#include<iostream>
#include<stdio.h>
using namespace std;
//class Solution {
//public:
//    void moveZeroes(vector<int>& nums) {
//        int dest = -1;
//        int cur = 0;
//        int size = nums.size();
//        //[0,dest]  [dest+1,cur-1] [cur ,n-1]
//        //  ����         0             ������
//        while (cur != size)
//        {
//            if (nums[cur] == 0)
//            {
//                ++cur;
//            }
//            else
//            {
//                ++dest;
//                swap(nums[dest], nums[cur]);
//                ++cur;
//            }
//        }
//    }
//};
//
//class Solution {
//public:
//    void moveZeroes(vector<int>& nums) {
//        for (int dest = -1, cur = 0; cur < nums.size(); cur++)
//            if (nums[cur])
//                swap(nums[++dest], nums[cur]);
//    }
//};
//#include<iostream>
//int main()
//{
//	/*auto num1 = "11";
//	auto endl=num1.size()-1;
//	std::cout << endl;*/
//	std::cout <<  3-'0';
//	return 0;
//}

//class Solution {
//public:
//    void duplicateZeros(vector<int>& arr) {
//        int cur = 0, dest = -1, n = arr.size();
//        //���ҵ���д�����һ����
//        while (cur < n)
//        {
//            if (arr[cur])
//                dest++;
//            else
//                dest += 2;
//            if (dest >= n - 1)
//                break;
//            cur++;
//        }
//        //�����߽����
//        if (dest == n)
//        {
//            arr[n - 1] = 0;
//            cur--; dest -= 2;
//        }
//        while (cur >= 0)
//        {
//            if (arr[cur])
//            {
//                arr[dest--] = arr[cur--];
//            }
//            else
//            {
//                arr[dest--] = 0;
//                arr[dest--] = 0;
//                cur--;
//            }
//        }
//    }
//};
//������
//class Solution {
//public:
//    int bitsum(int n)
//    {
//        int sum = 0;
//        while (n)
//        {
//            int t = n % 10;
//            sum += t * t;
//            n /= 10;
//        }
//        return sum;
//    }
//    bool isHappy(int n) {
//        int slow = n, fast = bitsum(n);
//        while (slow != fast)
//        {
//            slow = bitsum(slow);
//            fast = bitsum(bitsum(fast));
//        }
//        return slow == 1;
//    }
//};
//ʢˮ
//class Solution {
//public:
//    int maxArea(vector<int>& height) {
//        int left = 0, right = height.size() - 1, ret = 0;
//        while (left != right)
//        {
//            int v = min(height[left], height[right]) * (right - left);
//            ret = max(ret, v);
//            if (height[left] < height[right])
//            {
//                ++left;
//            }
//            else
//            {
//                --right;
//            }
//        }
//        return ret;
//    }
//};
// ��Ч�����θ���
//class Solution {
//public:
//    int triangleNumber(vector<int>& nums) {
//        sort(nums.begin(), nums.end());
//        int n = nums.size();
//        int ret = 0;
//        for (int i = n - 1; i >= 2; i--)
//        {
//            int left = 0, right = i - 1;
//            while (left < right)
//            {
//                if (nums[left] + nums[right] > nums[i])
//                {
//                    ret += right - left;
//                    --right;
//                }
//                else
//                    ++left;
//            }
//        }
//        return ret;
//    }
//};
//class Solution {
//public:
//    vector<int> twoSum(vector<int>& nums, int target) {
//        vector<int> sorted_nums = nums;
//        sort(sorted_nums.begin(), sorted_nums.end());
//        int left = 0, right = sorted_nums.size() - 1;
//        while (left < right)
//        {
//            int sum = sorted_nums[left] + sorted_nums[right];
//            if (sum > target)right--;
//            else if (sum < target)left++;
//            else
//                break;
//        }
//        vector<int> ret;
//        for (int i = 0; i < nums.size(); i++)
//        {
//            if (nums[i] == sorted_nums[left] || nums[i] == sorted_nums[right])
//            {
//                ret.push_back(i);
//            }
//            if (ret.size() == 2)
//            {
//                break;
//            }
//        }
//        return ret;
//    }
//};
//class Solution {
//public:
//    vector<vector<int>> threeSum(vector<int>& nums) {
//        vector<vector<int>> ret;
//        sort(nums.begin(), nums.end());
//        int n = nums.size();
//        for (int i = 0; i < n;) {
//            if (nums[i] > 0) break;
//            int left = i + 1, right = n - 1, target = -nums[i];
//            while (left < right) {
//                int sum = nums[left] + nums[right];
//                if (sum > target) --right;
//                else if (sum < target) ++left;
//                else {
//                    ret.push_back({ nums[i],nums[left],nums[right] });
//                    left++, right--;
//                    while (left < right && nums[left] == nums[left - 1]) ++left;
//                    while (left < right && nums[right] == nums[right + 1]) --right;
//                }
//            }
//            ++i;
//            while (i < n && nums[i] == nums[i - 1]) i++;
//        }
//        return ret;
//    }
//};

//class Solution {
//public:
//    vector<vector<int>> fourSum(vector<int>& nums, int target) {
//        sort(nums.begin(), nums.end());
//        vector<vector<int>> ret;
//        int n = nums.size();
//        for (int i = 0; i < n;)
//        {
//            // if(nums[i]>0) break;
//            for (int j = i + 1; j < n;)
//            {
//                int left = j + 1, right = n - 1;
//                long long a = nums[i], b = nums[j];
//                while (left < right)
//                {
//                    long long sum = nums[left] + nums[right];
//                    if (sum > target - a - b)
//                    {
//                        --right;
//                    }
//                    else if (sum < target - a - b)
//                    {
//                        ++left;
//                    }
//                    else
//                    {
//                        ret.push_back({ nums[i],nums[j],nums[left],nums[right] });
//                        ++left;
//                        --right;
//                        while (left < right && nums[left] == nums[left - 1]) ++left;
//                        while (left < right && nums[right] == nums[right + 1])--right;
//                    }
//                }
//                j++;
//                while (j < n && nums[j] == nums[j - 1])j++;
//            }
//            i++;
//            while (i < n && nums[i] == nums[i - 1])i++;
//        }
//        return ret;
//    }
//};
//class Solution {
//public:
//    int minSubArrayLen(int target, vector<int>& nums) {
//        int n = nums.size(), sum = 0, len = INT_MAX;
//        for (int left = 0, right = 0; right < n; right++)
//        {
//            sum += nums[right];
//            while (sum >= target)
//            {
//                len = min(len, right - left + 1);
//                sum -= nums[left++];
//            }
//        }
//        return len == INT_MAX ? 0 : len;
//    }
//};
//
//class Solution {
//public:
//    int lengthOfLongestSubstring(string s) {
//        int hash[128] = { 0 };
//        int left = 0, right = 0, n = s.size();
//        int ret = 0;
//        while (right < n)
//        {
//            hash[s[right]]++;//���봰��
//            while (hash[s[right]] > 1) hash[s[left++]]--;
//            ret = max(ret, right - left + 1);
//            right++;
//        }
//        return ret;
//    }
//};

//class Solution {
//public:
//    int longestOnes(vector<int>& nums, int k) {
//        int left = 0, right = 0;
//        int ret = 0, zero = 0;
//        while (nums.size() > right)
//        {
//            if (nums[right] == 0) zero++;
//            while (zero > k) {
//                if (nums[left++] == 0) zero--;
//            }
//            ret = max(ret, right - left + 1);
//            right++;
//        }
//        return ret;
//    }
//};

//��x����0
//class Solution {
//public:
//    int minOperations(vector<int>& nums, int x) {
//        int sum = 0;
//        for (auto e : nums) sum += e;
//        int target = sum - x;
//        if (target < 0)
//        {
//            return -1;
//        }
//        int ret = -1;
//        for (int right = 0, left = 0, tmp = 0; right < nums.size(); right++)
//        {
//            tmp += nums[right];
//            while (tmp > target)
//            {
//                tmp -= nums[left++];
//            }
//            if (tmp == target)
//                ret = max(ret, right - left + 1);
//        }
//        if (ret == -1)
//            return -1;
//        else return nums.size() - ret;
//    }
//};

//class Solution {
//public:
//    int totalFruit(vector<int>& fruits) {
//        //unordered_map<int,int> hash;
//        int hash[100001] = { 0 };
//        int ret = 0;
//        for (int left = 0, right = 0, kind = 0; right < fruits.size(); right++)
//        {
//            if (hash[fruits[right]] == 0) kind++;
//            hash[fruits[right]]++;
//            while (kind > 2)
//            {
//                hash[fruits[left]]--;
//                if (hash[fruits[left]] == 0)
//                    //hash.erase(fruits[left]);
//                    kind--;
//                left++;
//            }
//            ret = max(ret, right - left + 1);
//        }
//        return ret;
//    }
//};
//class Solution {
//public:
//    vector<int> findAnagrams(string s, string p) {
//        int hash1[26] = { 0 };
//        for (auto e : p) hash1[e - 'a']++;
//        int hash2[26] = { 0 };
//        int plen = p.size();
//        vector<int> ret;
//        for (int right = 0, left = 0, count = 0; right < s.size(); right++)
//        {
//            char in = s[right];
//            if (++hash2[in - 'a'] <= hash1[in - 'a']) count++;
//            if (right - left + 1 > plen)
//            {
//                //������
//                char out = s[left++];
//                if (hash2[out - 'a']-- <= hash1[out - 'a']) count--;
//            }
//            if (count == plen)
//            {
//                ret.push_back(left);
//            }
//        }
//        return ret;
//    }
//};

//class Solution {
//public:
//    int search(vector<int>& nums, int target) {
//        int left = 0, right = nums.size() - 1;
//        while (left <= right)
//        {
//            int Mid = (left + right) / 2;
//            if (nums[Mid] < target) left = Mid + 1;
//            else if (nums[Mid] > target) right = Mid - 1;
//            else return Mid;
//        }
//        return -1;
//    }
//};

//class Solution {
//public:
//    vector<int> searchRange(vector<int>& nums, int target) {
//        if (!nums.size()) return { -1,-1 };
//        int left = 0, right = nums.size() - 1;
//        int begin; int mid;
//        while (left < right)
//        {
//            //����˵�
//            mid = left + (right - left) / 2;
//            if (nums[mid] >= target) right = mid;
//            else left = mid + 1;
//        }
//        if (nums[left] != target) return { -1,-1 };
//        else begin = left;
//        right = nums.size() - 1;
//        while (left < right)
//        {
//            //���Ҷ˵�
//            mid = left + (right - left + 1) / 2;
//            if (nums[mid] > target) right = mid - 1;
//            else left = mid;
//        }
//        return { begin,right };
//    }
//};
//class Solution {
//public:
//    int mySqrt(int x) {
//        if (x < 1) return 0;
//        int left = 1, right = x;
//        long long mid;
//        while (left < right)
//        {
//            mid = left + (right - left + 1) / 2;
//            if (mid * mid <= x) left = mid;
//            else right = mid - 1;
//        }
//        return left;
//    }
//};

//class Solution {
//public:
//    int searchInsert(vector<int>& nums, int target) {
//        int left = 0, right = nums.size() - 1;
//        while (left < right)
//        {
//            int mid = left + (right - left) / 2;
//            if (nums[mid] >= target) right = mid ;
//            else left = mid + 1;
//        }
// if(nums[left]<target) return left + 1;
//        return left;
//    }
//};
//class Solution {
//public:
//    int peakIndexInMountainArray(vector<int>& arr) {
//        int right = arr.size() - 1, left = 0;
//        while (left < right)
//        {
//            int mid = left + (right - left + 1) / 2;
//            if (arr[mid] > arr[mid - 1]) left = mid;
//            else right = mid - 1;
//        }
//        return left;
//    }
//};
//#include <iostream>
//#include<vector>
//using namespace std;
//
//int main() {
//    int n, q;
//    cin >> n >> q;
//    vector<int> arrn(n + 1, 0);
//    for (int i = 1; i <= n; i++)
//    {
//        cin >> arrn[i];
//    }
//    vector<long long> dp(n + 1, 0);
//    for (int i = 1; i <= n; i++)
//    {
//        dp[i] = arrn[i] + dp[i - 1];
//    }
//    while (q--)
//    {
//        int l, r;
//        cin >> l >> r;
//        cout << dp[r] - dp[l - 1] << endl;
//    }
//
//    return 0;
//}
//#include <iostream>
//#include<vector>
//using namespace std;
//
//int main() {
//    int n, m, q;
//    cin >> n >> m >> q;
//    vector<vector<int>> arr(n + 1, vector<int>(m + 1));
//    for (int i = 1; i <= n; i++)
//        for (int j = 1; j <= m; j++)
//            cin >> arr[i][j];
//    vector<vector<long long>> dp(n + 1, vector<long long>(m + 1));
//    for (int i = 1; i <= n; i++)
//    {
//        for (int j = 1; j <= m; j++)
//        {
//            dp[i][j] = dp[i - 1][j] + dp[i][j - 1] + arr[i][j] - dp[i - 1][j - 1];
//        }
//    }
//    int x1, y1, x2, y2;
//    while (q--)
//    {
//        cin >> x1 >> y1 >> x2 >> y2;
//        cout << dp[x2][y2] - dp[x1 - 1][y2] - dp[x2][y1 - 1] + dp[x1 - 1][y1 - 1] << endl;
//    }
//}
//class Solution {
//public:
//    int pivotIndex(vector<int>& nums) {
//        int n = nums.size();
//        vector<int> f(n), g(n);
//        for (int i = 1; i < n; i++)
//            f[i] = f[i - 1] + nums[i - 1];
//        for (int i = n - 2; i >= 0; i--)
//            g[i] = g[i + 1] + nums[i + 1];
//        for (int i = 0; i < n; i++)
//        {
//            if (g[i] == f[i])
//                return i;
//        }
//        return -1;
//    }
//};class Solution {
//public:
//    int pivotIndex(vector<int>& nums) {
//        int totalSum = 0, leftSum = 0;
//        for (auto num : nums)
//            totalSum += num;
//        for (int i = 0; i < nums.size(); i++)
//        {
//            if (leftSum == totalSum - leftSum - nums[i])
//                return i;
//            leftSum += nums[i];
//        }
//        return -1;
//    }
//};
//class Solution {
//public:
//    vector<int> productExceptSelf(vector<int>& nums) {
//        int n = nums.size();
//        vector<int> f(n), g(n);
//        f[0] = g[n - 1] = 1;
//        for (int i = 1; i < n; i++)
//            f[i] = f[i - 1] * nums[i - 1];
//        for (int i = n - 2; i >= 0; i--)
//            g[i] = g[i + 1] * nums[i + 1];
//        vector<int> ret(n);
//        for (int i = 0; i < n; i++)
//            ret[i] = g[i] * f[i];
//        return ret;
//    }
//};
//class Solution {
//public:
//    int subarraySum(vector<int>& nums, int k) {
//        unordered_map<int, int> hash;
//        int sum = 0, ret = 0;
//        hash[0] = 1;
//        for (auto x : nums)
//        {
//            sum += x;
//            if (hash.count(sum - k)) ret += hash[sum - k];
//            hash[sum]++;
//        }
//        return ret;
//    }
//};
//class Solution {
//public:
//    int subarraysDivByK(vector<int>& nums, int k) {
//        unordered_map<int, int> hash;
//        hash[0 % k] = 1;
//        int sum = 0, ret = 0;
//        for (auto x : nums)
//        {
//            sum += x;
//            int r = (sum % k + k) % k;
//            if (hash.count(r)) ret += hash[r];
//            hash[r]++;
//        }
//        return ret;
//    }
//};
//class Solution {
//public:
//    int findMaxLength(vector<int>& nums) {
//        unordered_map<int, int>hash;
//        hash[0] = -1;
//        int sum = 0, ret = 0;
//        for (int i = 0; i < nums.size(); ++i)
//        {
//            sum += nums[i] == 0 ? -1 : 1;
//            if (hash.count(sum))
//                ret = max(ret, i - hash[sum]);
//            else
//                hash[sum] = i;
//        }
//        return ret;
//    }
//};
//class Solution {
//public:
//    int findMaxLength(vector<int>& nums) {
//        unordered_map<int, int>hash{ {0,-1} };
//        int cur = 0, len = 0;
//        for (int i = 0; i < nums.size(); ++i)
//        {
//            nums[i] == 0 ? cur-- : cur++;
//            if (hash.count(cur))
//            {
//                len = max(len, i - hash[cur]);
//            }
//            else
//            {
//                hash[cur] = i;
//            }
//        }
//        return len;
//    }
//};
//class Solution {
//public:
//    vector<vector<int>> matrixBlockSum(vector<vector<int>>& mat, int k)
//    {
//        int m = mat.size(), n = mat[0].size();
//        vector<vector<int>>dp(m + 1, vector<int>(n + 1));
//        for (int i = 1; i <= m; i++)
//        {
//            for (int j = 1; j <= n; j++)
//            {
//                dp[i][j] = dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1] + mat[i - 1][j - 1];
//            }
//        }
//        vector<vector<int>> answer(m, vector<int>(n));
//        for (int i = 0; i < m; i++)
//        {
//            for (int j = 0; j < n; j++)
//            {
//                int x1 = max(0, i - k) + 1, y1 = max(0, j - k) + 1;
//                int x2 = min(m - 1, i + k) + 1, y2 = min(n - 1, j + k) + 1;
//                answer[i][j] = dp[x2][y2] - dp[x1 - 1][y2] - dp[x2][y1 - 1] + dp[x1 - 1][y1 - 1];
//            }
//        }
//        return answer;
//    }
//};
//class Solution {
//public:
//    int hammingWeight(int n) {
//        int count = 0;
//        while (n > 0)
//        {
//            count += n & 1;
//            n >>= 1;
//        }
//        return count;
//    }
//};
//class Solution {
//public:
//    int hammingWeight(int n) {
//        int res = 0;
//        while (n)
//        {
//            res++;
//            n &= n - 1;
//        }
//        return res;
//    }
//};
//class Solution {
//public:
//    vector<int> countBits(int n) {
//        vector<int> ans(n + 1, 0);
//        for (int i = 1; i <= n; i++)
//        {
//            ans[i] = ans[i & i - 1] + 1;
//        }
//        return ans;
//    }
//};
//class Solution {
//public:
//    int hammingDistance(int x, int y) {
//        int m = x ^ y;
//        int count = 0;
//        while (m)
//        {
//            m &= m - 1;
//            count++;
//        }
//        return count;
//    }
//};
//class Solution {
//public:
//    int singleNumber(vector<int>& nums) {
//        int n = 0;
//        for (int i = 0; i < nums.size(); i++)
//        {
//
//            n ^= nums[i];
//        }
//        return n;
//    }
//};
//class Solution {
//public:
//    vector<int> singleNumber(vector<int>& nums) {
//        int totall = 0;
//        for (auto x : nums)
//        {
//            totall ^= x;
//        }
//
//        unsigned int lowbit = totall & (-(unsigned int)totall);
//        int num1 = 0, num2 = 0;
//        for (auto x : nums)
//        {
//            if (lowbit & x)
//                num1 ^= x;
//            else
//                num2 ^= x;
//        }
//        return { num1,num2 };
//    }
//};
//int main()
//{
//	int a = 10;
//	int b = 20;
//	int c = a + b;
//	cout << c;
//	return 0;
//}
//class Solution {
//public:
//    bool isUnique(string astr) {
//        //��1
//        unordered_map<char, int> hash(101);
//        for (auto e : astr)
//        {
//            hash[e]++;
//            if (hash[e] > 1)
//                return false;
//        }
//
//        return true;
//    }
//};
//class Solution {
//public:
//    bool isUnique(string astr) {
//        if (astr.size() > 26)
//            return false;
//        int bitmap = 0;
//        for (auto ch : astr)
//        {
//            int i = ch - 'a';
//            if ((bitmap >> i) & 1 == 1) return false;
//            bitmap |= 1 << i;
//        }
//        return true;
//    }
//};
//class Solution {
//public:
//    int missingNumber(vector<int>& nums) {
//        unordered_set<int> hashset;
//        for (auto e : nums)
//        {
//            hashset.insert(e);
//        }
//        for (int i = 0; i <= nums.size(); i++)
//        {
//            if (hashset.find(i) == hashset.end())
//            {
//                return i;
//            }
//        }
//        return -1;
//    }
//};
//class Solution {
//public:
//    int missingNumber(vector<int>& nums) {
//        int ret = 0;
//        for (auto e : nums)
//        {
//            ret ^= e;
//        }
//        for (int i = 0; i <= nums.size(); i++)
//        {
//            ret ^= i;
//        }
//        return ret;
//    }
//};
//class Solution {
//public:
//    int getSum(int a, int b) {
//        while (b != 0)
//        {
//            int carry = (a & b) << 1;
//            a ^= b;
//            b = carry;
//        }
//        return a;
//    }
//};
//class Solution {
//public:
//    int singleNumber(vector<int>& nums) {
//        int ret = 0;
//        for (int i = 0; i < 32; i++)
//        {
//            int sum = 0;
//            for (auto x : nums)
//                if ((x >> i) & 1 == 1)
//                    sum++;
//            sum %= 3;
//            if (sum == 1)
//                ret |= (1 << i);
//        }
//        return ret;
//    }
//};
//class Solution {
//public:
//    vector<int> missingTwo(vector<int>& nums) {
//        int tmp = 0;
//        for (auto x : nums) tmp ^= x;
//        for (int i = 1; i <= nums.size() + 2; i++) tmp ^= i;
//        int diff = 0;
//        while (1)
//        {
//            if (((tmp >> diff) & 1) == 1) break;
//            else diff++;
//        }
//        int b = 0, a = 0;
//        for (auto x : nums)
//            if (((x >> diff) & 1) == 1) b ^= x;
//            else a ^= x;
//        for (int i = 1; i <= nums.size() + 2; i++)
//            if (((i >> diff) & 1) == 1)b ^= i;
//            else a ^= i;
//        return{ a,b };
//    }
//};
//class Solution {
//public:
//    string modifyString(string s) {
//        int n = s.size();
//        for (int i = 0; i < n; i++)
//        {
//            if (s[i] == '?')
//            {
//                for (char ch = 'a'; ch <= 'z'; ch++)
//                {
//                    if ((i == 0 || ch != s[i - 1]) && (i == n - 1 || ch != s[i + 1]))
//                    {
//                        s[i] = ch;
//                        break;
//                    }
//                }
//            }
//        }
//        return s;
//    }
//};
//class Solution {
//public:
//    int findPoisonedDuration(vector<int>& timeSeries, int duration) {
//        int ret = 0;
//        for (int i = 1; i < timeSeries.size(); i++)
//        {
//            int x = timeSeries[i] - timeSeries[i - 1];
//            if (x >= duration)
//            {
//                ret += duration;
//            }
//            else
//            {
//                ret += x;
//            }
//        }
//        return ret + duration;
//    }
//};
//class Solution {
//public:
//    string convert(string s, int numRows) {
//        if (numRows == 1)
//            return s;
//        string str;
//        int d = 2 * numRows - 2, n = s.size();
//        //������һ��
//        for (int i = 0; i < n; i += d)
//        {
//            str += s[i];
//        }
//        //�����м���
//        for (int x = 1; x < numRows - 1; x++)
//        {
//            for (int k = x, j = d - x; k < n || j < n; k += d, j += d)
//            {
//                if (k < n) str += s[k];
//                if (j < n)str += s[j];
//            }
//        }
//        //�������һ��
//        for (int m = numRows - 1; m < n; m += d)
//        {
//            str += s[m];
//        }
//        return str;
//    }
//};
//class Solution {
//public:
//    string countAndSay(int n) {
//        string ret = "1";
//        for (int i = 1; i < n; i++)
//        {
//            string tmp;
//            int len = ret.size();
//            for (int left = 0, right = 0; right < len;)
//            {
//                while (right < len && ret[right] == ret[left])right++;
//                tmp += to_string(right - left) + ret[left];
//                left = right;
//            }
//            ret = tmp;
//        }
//        return ret;
//    }
//};
//class Solution {
//public:
//    int minNumberOfFrogs(string croakOfFrogs) {
//        string t = "croak";
//        int n = t.size();
//        vector<int> hash(n);
//        unordered_map<char, int> index;
//        for (int i = 0; i < n; i++)
//            index[t[i]] = i;
//        for (auto ch : croakOfFrogs)
//        {
//            if (ch == 'c')
//            {
//                if (hash[n - 1] != 0) hash[n - 1]--;
//                hash[0]++;
//            }
//            else
//            {
//                int i = index[ch];
//                if (hash[i - 1] == 0) return -1;
//                hash[i - 1]--, hash[i]++;
//            }
//        }
//        for (int i = 0; i < n - 1; i++)
//        {
//            if (hash[i] != 0)
//            {
//                return -1;
//            }
//        }
//        return hash[n - 1];
//    }
//};
//class Solution {
//public:
//    void sortColors(vector<int>& nums) {
//        for (int i = 0, right = nums.size(), left = -1; i < right;)
//        {
//            if (nums[i] == 0)
//            {
//                swap(nums[++left], nums[i++]);
//            }
//            else if (nums[i] == 1)
//            {
//                i++;
//            }
//            else if (nums[i] == 2)
//            {
//                swap(nums[--right], nums[i]);
//            }
//        }
//    }
//};
//class Solution {
//public:
//    vector<int> sortArray(vector<int>& nums) {
//        srand(time(NULL));
//        qsort(nums, 0, nums.size() - 1);
//        return nums;
//    }
//    void qsort(vector<int>& nums, int l, int r)
//    {
//        if (l >= r) return;
//        int key = GetRandom(nums, l, r);
//        int i = l, right = r + 1, left = l - 1;
//        while (i < right)
//        {
//            if (nums[i] < key)
//            {
//                swap(nums[++left], nums[i++]);
//            }
//            else if (nums[i] == key)
//            {
//                i++;
//            }
//            else
//                swap(nums[--right], nums[i]);
//        }
//        qsort(nums, l, left);
//        qsort(nums, right, r);
//    }
//    int GetRandom(vector<int>& nums, int left, int right)
//    {
//        int r = rand();
//        return nums[r % (right - left + 1) + left];
//    }
//};
//class Solution {
//public:
//    int findKthLargest(vector<int>& nums, int k) {
//        int result = 0;
//        int n = nums.size();
//        if (n == 0 || k > n)
//            return 0;
//        priority_queue<int, vector<int>, greater<int>> store;
//        for (int i = 0; i < n; i++)
//        {
//            store.push(nums[i]);
//            if (store.size() > k)
//                store.pop();
//        }
//        result = store.top();
//        return result;
//    }
//};
//class Solution {
//public:
//    int findKthLargest(vector<int>& nums, int k) {
//        srand(time(NULL));
//        return qsort(nums, 0, nums.size() - 1, k);
//
//    }
//    int qsort(vector<int>& nums, int l, int r, int k)
//    {
//        if (l == r)
//            return nums[l];
//        int i = l, left = l - 1, right = r + 1;
//        int key = GetRandom(nums, l, r);
//        while (i < right)
//        {
//            if (nums[i] < key) swap(nums[++left], nums[i++]);
//            else if (nums[i] == key) i++;
//            else swap(nums[--right], nums[i]);
//        }
//        int c = r - right + 1, b = right - left - 1;
//        if (c >= k) return qsort(nums, right, r, k);
//        else if (b + c >= k) return key;
//        else return qsort(nums, l, left, k - b - c);
//    }
//    int GetRandom(vector<int>& nums, int left, int right)
//    {
//        int r = rand();
//        return nums[r % (right - left + 1) + left];
//    }
//};
//class Solution {
//public:
//    vector<int> smallestK(vector<int>& arr, int k) {
//        //����һ������
//        // sort(arr.begin(),arr.end());
//        // while(arr.size() > k)
//        // {
//        //     arr.pop_back();
//        // }
//        // return arr;
//
//        //������:����
//        //2.1С���
//        // vector<int> ans;
//        // priority_queue<int,vector<int>,greater<int>> nums;
//        // for(auto e : arr)
//        // {
//        //     nums.push(e);
//        // }
//        // while(k--)
//        // {
//        //     ans.push_back(nums.top());
//        //     nums.pop();
//        // }
//        // return ans;
//
//        //2.2���
//        // vector<int> ans;
//        // if(k==0)
//        // {
//        //     return ans;
//        // }
//        // priority_queue<int> nums;
//        // for(int i = 0;i<k;i++)
//        // {
//        //     nums.push(arr[i]);
//        // }
//        // for(int i = k ;i<arr.size();i++)
//        // {
//        //     if(arr[i]<nums.top())
//        //     {
//        //         nums.pop();
//        //         nums.push(arr[i]);
//        //     } 
//        // }
//        // while(!nums.empty())
//        //     {
//        //         ans.push_back(nums.top());
//        //         nums.pop();
//        //     }
//        // return ans;
//
//        //��������ѡ���㷨
//        srand(time(NULL));
//        qsort(arr, 0, arr.size() - 1, k);
//        return { arr.begin(),arr.begin() + k };
//    }
//    void qsort(vector<int>& arr, int l, int r, int k)
//    {
//        if (l >= r)
//            return;
//        int left = l - 1, right = r + 1, i = l;
//        int key = GetRandom(arr, l, r);
//        while (i < right)
//        {
//            if (key > arr[i]) swap(arr[++left], arr[i++]);
//            else if (key == arr[i]) i++;
//            else swap(arr[--right], arr[i]);
//        }
//        int a = left - l + 1, b = right - left - 1;
//        if (a > k)  qsort(arr, l, left, k);
//        else if (a + b >= k)return;
//        else  qsort(arr, right, r, k - a - b);
//    }
//    int GetRandom(vector<int>& arr, int left, int right) {
//        return arr[rand() % (right - left + 1) + left];
//    }
//
//};

//class Solution {
//    vector<int>tmp;
//public:
//    vector<int> sortArray(vector<int>& nums) {
//        tmp.resize(nums.size());
//        mergeSort(nums, 0, nums.size() - 1);
//        return nums;
//    }
//    void mergeSort(vector<int>& nums, int left, int right)
//    {
//        if (left >= right) return;
//        int mid = (left + right) >> 1;
//
//        mergeSort(nums, left, mid);
//        mergeSort(nums, mid + 1, right);
//        int cur1 = left, cur2 = mid + 1, i = 0;
//        while (cur1 <= mid && cur2 <= right)
//        {
//            tmp[i++] = nums[cur1] <= nums[cur2] ? nums[cur1++] : nums[cur2++];
//        }
//        while (cur1 <= mid) tmp[i++] = nums[cur1++];
//        while (cur2 <= right) tmp[i++] = nums[cur2++];
//        for (int i = left; i <= right; i++)
//        {
//            nums[i] = tmp[i - left];
//        }
//    }
//};
//class Solution {
//public:
//    int minimizedStringLength(string s) {
//        //��һ������
//        // sort(s.begin(),s.end());
//        // int count = 0;
//        // for(int i =0;i<s.size();i++)
//        // {
//        //     int j = i+1;
//        //     if(s[i]!=s[i+1]) count++;
//        // }
//        // return count;
//
//        // ��������ϣ��
//        return unordered_set<char>(s.begin(), s.end()).size();
//    }
//};
//class Solution {
//    int tmp[50010];
//public:
//    int reversePairs(vector<int>& nums) {
//        return mergeSort(nums, 0, nums.size() - 1);
//    }
//    int mergeSort(vector<int>& nums, int left, int right)
//    {
//        if (left >= right) return 0;
//        int ret = 0;
//        //1.���е�;
//        int mid = (left + right) >> 1;
//        //  2.��+������+����
//        ret += mergeSort(nums, left, mid);
//        ret += mergeSort(nums, mid + 1, right);
//        int cur1 = left, cur2 = mid + 1, i = 0;
//        //3.ʵ������
//        while (cur1 <= mid && cur2 <= right)
//        {
//            if (nums[cur1] <= nums[cur2]) tmp[i++] = nums[cur1++];
//            else {
//                ret += mid - cur1 + 1;
//                tmp[i++] = nums[cur2++];
//            }
//        }
//        while (cur1 <= mid) tmp[i++] = nums[cur1++];
//        while (cur2 <= right) tmp[i++] = nums[cur2++];
//        for (int j = left; j <= right; j++)
//        {
//            nums[j] = tmp[j - left];
//        }
//        return ret;
//    }
//};
//class Solution {
//public:
//    vector<int> ret;
//    vector<int> tmp;
//    vector<int> index;
//    vector<int> myindex;
//    vector<int> countSmaller(vector<int>& nums) {
//        int n = nums.size();
//        ret.resize(n), tmp.resize(n), index.resize(n), myindex.resize(n);
//        for (int i = 0; i < n; i++)
//        {
//            index[i] = i;
//        }
//        mergeSort(nums, 0, n - 1);
//        return ret;
//    }
//    void mergeSort(vector<int>& nums, int left, int right)
//    {
//        if (left >= right) return;
//        int mid = (right + left) >> 1;
//        mergeSort(nums, left, mid);
//        mergeSort(nums, mid + 1, right);
//        int cur1 = left, cur2 = mid + 1, i = 0;
//        while (cur1 <= mid && cur2 <= right)
//        {
//            if (nums[cur1] > nums[cur2])
//            {
//                ret[index[cur1]] += right - cur2 + 1;
//                tmp[i] = nums[cur1];
//                myindex[i++] = index[cur1++];
//            }
//            else
//            {
//                tmp[i] = nums[cur2];
//                myindex[i++] = index[cur2++];
//            }
//        }
//        while (cur1 <= mid)
//        {
//            tmp[i] = nums[cur1];
//            myindex[i++] = index[cur1++];
//        }
//        while (cur2 <= right)
//        {
//            tmp[i] = nums[cur2];
//            myindex[i++] = index[cur2++];
//        }
//        for (int i = left; i <= right; i++)
//        {
//            nums[i] = tmp[i - left];
//            index[i] = myindex[i - left];
//        }
//    }
//};
//class Solution {
//    int tmp[50010];
//public:
//    int reversePairs(vector<int>& nums) {
//        //����
//        return mergeSort(nums, 0, nums.size() - 1);
//    }
//    int mergeSort(vector<int>& nums, int left, int right)
//    {
//        int ret = 0;
//        if (left >= right) return 0;
//
//        int mid = (left + right) >> 1;
//        ret += mergeSort(nums, left, mid);
//        ret += mergeSort(nums, mid + 1, right);
//
//        int cur1 = left, cur2 = mid + 1, i = left;
//        while (cur1 <= mid)
//        {
//            while (cur2 <= right && nums[cur1] / 2.0 <= nums[cur2]) cur2++;
//            if (cur2 > right) break;
//            ret += right - cur2 + 1;
//            cur1++;
//        }
//        cur1 = left, cur2 = mid + 1;
//        while (cur1 <= mid && cur2 <= right)
//            tmp[i++] = nums[cur1] <= nums[cur2] ? nums[cur2++] : nums[cur1++];
//        while (cur1 <= mid) tmp[i++] = nums[cur1++];
//        while (cur2 <= right) tmp[i++] = nums[cur2++];
//        for (int j = left; j <= right; j++)
//            nums[j] = tmp[j];
//        return ret;
//
//    }
//};
//class Solution {
//    int tmp[50010];
//
//public:
//    int reversePairs(vector<int>& nums) {
//        // ����
//        return mergeSort(nums, 0, nums.size() - 1);
//    }
//    int mergeSort(vector<int>& nums, int left, int right) {
//        int ret = 0;
//        if (left >= right)
//            return 0;
//
//        int mid = (left + right) >> 1;
//        ret += mergeSort(nums, left, mid);
//        ret += mergeSort(nums, mid + 1, right);
//
//        int cur1 = left, cur2 = mid + 1, i = left;
//        while (cur2 <= right) {
//            while (cur1 <= mid && nums[cur1] / 2.0 <= nums[cur2])
//                cur1++;
//            if (cur1 > mid)
//                break;
//            ret += mid - cur1 + 1;
//            cur2++;
//        }
//        cur1 = left, cur2 = mid + 1;
//        while (cur1 <= mid && cur2 <= right)
//            tmp[i++] = nums[cur1] <= nums[cur2] ? nums[cur1++] : nums[cur2++];
//        while (cur1 <= mid)
//            tmp[i++] = nums[cur1++];
//        while (cur2 <= right)
//            tmp[i++] = nums[cur2++];
//        for (int j = left; j <= right; j++)
//            nums[j] = tmp[j];
//        return ret;
//    }
//};
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
//class Solution {
//public:
//    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
//        ListNode* cur1 = l1, * cur2 = l2;
//        ListNode* newHead = new ListNode(0);
//        ListNode* tail = newHead;
//        int t = 0;
//        while (cur1 || cur2 || t)
//        {
//            if (cur1)
//            {
//                t += cur1->val;
//                cur1 = cur1->next;
//            }
//            if (cur2)
//            {
//                t += cur2->val;
//                cur2 = cur2->next;
//            }
//            tail->next = new ListNode(t % 10);
//            tail = tail->next;
//            t /= 10;
//        }
//        tail = newHead->next;
//        delete newHead;
//        return tail;
//    }
//};
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
//class Solution {
//public:
//    ListNode* reverseList(ListNode* head)
//    {
//        //ԭ�����ķ�ת
//        ListNode* n1 = nullptr, * n2 = head, * n3 = head->next;
//        while (n2)
//        {
//            n2->next = n1;
//            n1 = n2;
//            n2 = n3;
//            if (n3) n3 = n3->next;
//        }
//        return n1;
//    }
//    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
//        l1 = reverseList(l1);
//        l2 = reverseList(l2);
//        ListNode* cur1 = l1, * cur2 = l2;
//        ListNode* newHead = new ListNode(0);
//        ListNode* tail = newHead;
//        int t = 0;
//        while (cur1 || cur2 || t)
//        {
//            if (cur1)
//            {
//                t += cur1->val;
//                cur1 = cur1->next;
//            }
//            if (cur2)
//            {
//                t += cur2->val;
//                cur2 = cur2->next;
//            }
//            tail->next = new ListNode(t % 10);
//            tail = tail->next;
//            t /= 10;
//        }
//        reverseList(l1);
//        reverseList(l2);
//        tail = newHead->next;
//        delete newHead;
//        return reverseList(tail);
//    }
//};
//#include<stdio.h>
//int main()
//{
//	int i;
//	int x , max;
//	printf("�����1������:");
//	cin >> x;
//	max = x;
//	for (i = 1; i <= 9; i++)
//	{
//		printf("�����%d������", i +1);
//		cin >> x;
//		if (x > max)
//		{
//			max = x;
//		}
//	}
//	printf("��������%d", max);
//	return 0;
//}
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
//class Solution {
//public:
//    ListNode* swapPairs(ListNode* head) {
//        if (!head || !head->next) return head;
//        ListNode* newhead = new ListNode(-1);
//        newhead->next = head;
//        ListNode* prev = newhead, * cur = prev->next, * next = cur->next, * nnext = next->next;
//        while (cur && next)
//        {
//            prev->next = next;
//            next->next = cur;
//            cur->next = nnext;
//            prev = cur;
//            cur = nnext;
//            if (cur)next = cur->next;
//            if (next)nnext = next->next;
//        }
//        cur = newhead->next;
//        delete newhead;
//        return cur;
//    }
//};
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
//class Solution {
//    //�ҵ��м�ڵ�
//    ListNode* Midlist(ListNode* head) {
//        ListNode* fast = head, * slow = head;
//        while (fast && fast->next)
//        {
//            fast = fast->next->next;
//            slow = slow->next;
//        }
//        return slow;
//    }
//    //��ת����
//    ListNode* reverseList(ListNode* head)
//    {
//        ListNode* n1 = nullptr, * n2 = head, * n3;
//        while (n2)
//        {
//            n3 = n2->next;
//            n2->next = n1;
//            n1 = n2;
//            n2 = n3;
//            //if(n3) n3 = n3->next;
//        }
//        return n1;
//    }//�ϲ�������������
//    void mergeTwoLists(ListNode* list1, ListNode* list2) {
//        while (list2)
//        {
//            ListNode* temp1 = list1->next;
//            ListNode* temp2 = list2->next;
//
//            list1->next = list2;
//            list2->next = temp1;
//            //temp1->next = temp2;
//            list1 = temp1;
//            list2 = temp2;
//        }
//    }
//public:
//    void reorderList(ListNode* head) {
//        if (!head || !head->next) return;
//
//        ListNode* mid = Midlist(head);
//        ListNode* secondHalf = mid->next;
//        mid->next = nullptr;
//        ListNode* RList = reverseList(secondHalf);
//        mergeTwoLists(head, RList);
//    }
//};
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
//class Solution {
//    //�ҵ��м�ڵ�
//    ListNode* Midlist(ListNode* head) {
//        ListNode* fast = head, * slow = head;
//        while (fast && fast->next)
//        {
//            fast = fast->next->next;
//            slow = slow->next;
//        }
//        return slow;
//    }
//    //��ת����
//    //1.��ָ��
//    // ListNode* reverseList(ListNode * head)
//    // {
//    //     ListNode * n1 = nullptr,*n2 = head,*n3 ;
//    //     while(n2)
//    //     {
//    //         n3 = n2->next;
//    //         n2->next = n1;
//    //         n1 = n2;
//    //         n2 =n3;
//    //         //if(n3) n3 = n3->next;
//    //     }
//    //     return n1;
//    // }
//    //2.ͷ�巨
//    ListNode* reverseList(ListNode* head)
//    {
//        ListNode* ret = new ListNode(0);
//        ListNode* prev = ret;
//        prev->next = nullptr;
//        ListNode* cur1 = head;
//        while (cur1)
//        {
//            ListNode* next = cur1->next;
//            cur1->next = prev->next;
//            prev->next = cur1;
//            cur1 = next;
//        }
//        cur1 = prev->next;
//        delete prev;
//        return cur1;
//    }
//    //�ϲ�������������
//    void mergeTwoLists(ListNode* list1, ListNode* list2) {
//        while (list2)
//        {
//            ListNode* temp1 = list1->next;
//            ListNode* temp2 = list2->next;
//
//            list1->next = list2;
//            list2->next = temp1;
//            //temp1->next = temp2;
//            list1 = temp1;
//            list2 = temp2;
//        }
//    }
//public:
//    void reorderList(ListNode* head) {
//        if (!head || !head->next) return;
//
//        ListNode* mid = Midlist(head);
//        ListNode* secondHalf = mid->next;
//        mid->next = nullptr;
//        ListNode* RList = reverseList(secondHalf);
//        mergeTwoLists(head, RList);
////    }
//};
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
//class Solution {
//    struct cmp {
//        bool operator()(const ListNode* l1, const ListNode* l2) {
//            return l1->val > l2->val;
//        }
//    };
//
//public:
//    ListNode* mergeKLists(vector<ListNode*>& lists) {
//        priority_queue<ListNode*, vector<ListNode*>, cmp> heap;
//        for (auto l : lists) {
//            if (l)
//                heap.push(l);
//        }
//        ListNode* ret = new ListNode(-1);
//        ListNode* prev = ret;
//        while (!heap.empty()) {
//            ListNode* t = heap.top();
//            heap.pop();
//            prev->next = t;
//            prev = t;
//            if (t->next)
//                heap.push(t->next);
//        }
//        prev = ret->next;
//        delete ret;
//        return prev;
//    }
//};
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
//class Solution {
//public:
//    ListNode* mergeKLists(vector<ListNode*>& lists) {
//        return merge(lists, 0, lists.size() - 1);
//    }
//    ListNode* merge(vector<ListNode*>& lists, int left, int right) {
//        if (left > right)
//            return nullptr;
//        if (left == right)
//            return lists[left];
//        // �ҵ��м�ڵ�
//        int mid = (left + right) >> 1;
//        // �ݹ�
//        ListNode* l1 = merge(lists, left, mid);
//        ListNode* l2 = merge(lists, mid + 1, right);
//        // �ϲ���������
//        return mergeTwoLists(l1, l2);
//    }
//    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
//        if (l1 == nullptr)
//            return l2;
//        if (l2 == nullptr)
//            return l1;
//        // �����ĺϲ�
//        ListNode newhead;
//        ListNode* cur1 = l1, * cur2 = l2, * prev = &newhead;
//        newhead.next = nullptr;
//        while (cur1 && cur2) {
//            if (cur1->val <= cur2->val) {
//                prev = prev->next = cur1;
//                cur1 = cur1->next;
//            }
//            else {
//                prev = prev->next = cur2;
//                cur2 = cur2->next;
//            }
//        }
//        if (cur1)
//            prev->next = cur1;
//        if (cur2)
//            prev->next = cur2;
//        return newhead.next;
//    }
//};
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
//class Solution {
//public:
//    ListNode* reverseKGroup(ListNode* head, int k) {
//        //ͳ��ѭ����ת�Ĵ���
//        int n = 0;
//        ListNode* cur = head;
//        while (cur)
//        {
//            cur = cur->next;
//            n++;
//        }
//        n /= k;
//        //��תn��
//        cur = head;
//        ListNode* newhead = new ListNode(0);
//        ListNode* prev = newhead;
//        for (int i = 0; i < n; i++)
//        {
//            //ÿ�η�ת�����ĸ���
//            ListNode* tmp = cur; // ��¼��ת�ĵ�һ���ڵ�
//            for (int j = 0; j < k; j++)
//            {
//                ListNode* next = cur->next;
//                cur->next = prev->next;
//                prev->next = cur;
//                cur = next;
//            }
//            prev = tmp;
//        }
//        //����ʣ��ڵ�
//        prev->next = cur;
//        cur = newhead->next;
//        delete newhead;
//        return cur;
//    }
//};
//class Solution {
//public:
//    vector<int> twoSum(vector<int>& nums, int target) {
//        // �����ⷨ
//        vector<int> arr;
//        for (int i = 0; i < nums.size(); i++)
//        {
//            for (int j = i + 1; j < nums.size(); j++)
//            {
//                if (nums[i] + nums[j] == target)
//                {
//                    arr.push_back(i);
//                    arr.push_back(j);
//                }
//            }
//        }
//        return arr;
//    }
//};
//class Solution {
//public:
//    vector<int> twoSum(vector<int>& nums, int target) {
//        unordered_map<int, int> hash;
//        //int sum = 0;
//        for (int i = 0; i < nums.size(); i++)
//        {
//            int sum = target - nums[i];
//            if (hash.count(sum))
//            {
//                return { i,hash[sum] };
//            }
//            hash[nums[i]] = i;
//        }
//        return {};
//    }
//};
//class Solution {
//public:
//    bool CheckPermutation(string s1, string s2) {
//        if (s1.size() != s2.size())
//            return false;
//        vector<int> table(128, 0);
//        for (auto x : s1) {
//            table[x]++;
//        }
//        for (auto x : s2) {
//            table[x]--;
//            if (table[x] < 0)
//                return false;
//        }
//        return true;
//    }
//};
//class Solution {
//public:
//    bool CheckPermutation(string s1, string s2) {
//        if (s1.size() != s2.size()) return false;
//        sort(s1.begin(), s1.end());
//        sort(s2.begin(), s2.end());
//        return s1 == s2;
//    }
//};
//class Solution {
//public:
//    bool CheckPermutation(string s1, string s2) {
//        if (s1.size() != s2.size())
//            return false;
//        int hash[26] = { 0 };
//        for (auto ch : s1) {
//            hash[ch - 'a']++;
//        }
//        for (auto ch : s2) {
//            hash[ch - 'a']--;
//            if (hash[ch - 'a'] < 0)
//                return false;
//        }
//        return true;
//    }
//};
//class Solution {
//public:
//    bool containsDuplicate(vector<int>& nums) {
//        unordered_set<int>hash;
//        for (auto x : nums)
//        {
//            if (hash.find(x) != hash.end()) return true;
//            hash.insert(x);
//        }
//        return false;
//    }
//};
//class Solution {
//public:
//    bool containsNearbyDuplicate(vector<int>& nums, int k) {
//        unordered_map<int, int> hash;
//        for (int i = 0; i < nums.size(); i++) {
//            if (hash.count(nums[i])) {
//                if (i - hash[nums[i]] <= k)
//                    return true;
//            }
//            hash[nums[i]] = i;
//        }
//        return false;
//    }
//};
//class Solution {
//public:
//    vector<vector<string>> groupAnagrams(vector<string>& strs) {
//        unordered_map<string, vector<string>>hash;
//        for (auto str : strs)
//        {
//            string key = str;
//            sort(key.begin(), key.end());
//            hash[key].push_back(str);
//        }
//        vector<vector<string>>ret;
//        for (auto [x, y] : hash)
//        {
//            ret.push_back(y);
//        }
//        return ret;
//    }
//};
//class Solution {
//    string commonPrefix(string& str1, string& str2)
//    {
//        int len = min(str1.size(), str2.size());
//        int i = 0;
//        while (i < len && str1[i] == str2[i])
//        {
//            i++;
//        }
//        return str1.substr(0, i);
//    }
//public:
//    string longestCommonPrefix(vector<string>& strs) {
//        //�����Ƚ�
//        if (strs.empty()) return "";
//        string perfix = strs[0];
//        for (int i = 1; i < strs.size(); ++i)
//        {
//            perfix = commonPrefix(perfix, strs[i]);
//            if (perfix.empty()) break;
//        }
//        return perfix;
//
//    }
//};
//class Solution {
//public:
//    string longestCommonPrefix(vector<string>& strs) {
//        // �ⷨ��������Ƚ�
//        for (int i = 0; i < strs[0].size(); i++) {
//            char tmp = strs[0][i];
//            for (int j = 1; j < strs.size(); j++) {
//                if (i == strs[j].size() || tmp != strs[j][i])
//                    return strs[0].substr(0, i);
//            }
//        }
//        return strs[0];
//    }
//};
//class Solution {
//public:
//    string longestPalindrome(string s) {
//        int begin = 0, len = 0, n = s.size();
//
//        for (int i = 0; i < n; i++) {
//            int left = i, right = i;
//            while (left >= 0 && right < n && s[left] == s[right]) {
//                right++;
//                left--;
//                if (right - left - 1 > len) {
//                    begin = left + 1;
//                    len = right - left - 1;
//                }
//            }
//            left = i, right = i + 1;
//            while (left >= 0 && right < n && s[left] == s[right]) {
//                right++;
//                left--;
//                if (right - left - 1 > len) {
//                    begin = left + 1;
//                    len = right - left - 1;
//                }
//            }
//        }
//        return s.substr(begin, len);
//    }
//};
//class Solution {
//public:
//    string addBinary(string a, string b) {
//        string ret;
//        int cur1 = a.size() - 1, cur2 = b.size() - 1, t = 0;
//        while (cur1 >= 0 || cur2 >= 0 || t)
//        {
//            if (cur1 >= 0) t += a[cur1--] - '0';
//            if (cur2 >= 0) t += b[cur2--] - '0';
//            ret += t % 2 + '0';
//            t /= 2;
//        }
//        reverse(ret.begin(), ret.end());
//        return ret;
//    }
//};
//class Solution {
//public:
//    string multiply(string num1, string num2) {
//        int m = num1.size(), n = num2.size();
//        reverse(num1.begin(), num1.end());
//        reverse(num2.begin(), num2.end());
//        vector<int> tmp(m + n - 1);
//        for (int i = 0; i < m; i++)
//            for (int j = 0; j < n; j++) {
//                tmp[i + j] += (num1[i] - '0') * (num2[j] - '0');
//            }
//        string ret;
//        int cur = 0, t = 0;
//        while (cur < m + n - 1 || t) {
//            if (cur < m + n - 1)
//                t += tmp[cur++];
//            ret += t % 10 + '0';
//            t /= 10;
//        }
//        while (ret.size() > 1 && ret.back() == '0')
//            ret.pop_back();
//        reverse(ret.begin(), ret.end());
//        return ret;
//    }
//};
//class Solution {
//public:
//    string removeDuplicates(string s) {
//        string ret;
//        for (auto ch : s) {
//            if (!ret.empty() && ret.back() == ch)
//                ret.pop_back();
//            else
//                ret += ch;
//        }
//        return ret;
//    }
//};
//class Solution {
//public:
//    bool backspaceCompare(string s, string t) {
//        string ret1, ret2;
//        for (auto ch : s) {
//            if (!ret1.empty() && ch == '#')
//                ret1.pop_back();
//            else
//                if (ch != '#')
//                    ret1 += ch;
//        }
//        for (auto ch : t) {
//            if (!ret2.empty() && ch == '#')
//                ret2.pop_back();
//            else
//            {
//                if (ch != '#')
//                    ret2 += ch;
//            }
//        }
//        return ret1 == ret2;
//    }
//};class Solution {
//public:
//    bool backspaceCompare(string s, string t) {
//        return changeStr(s) == changeStr(t);
//    }
//    string changeStr(string s) {
//        string ret;
//        for (auto ch : s) {
//            if (ch != '#')
//                ret += ch;
//            else {
//                if (!ret.empty())
//                    ret.pop_back();
//            }
//        }
//        return ret;
//    }
//};
// int main()
// {
//     return 0;
// }
//class Solution {
//public:
//    int calculate(string s) {
//        vector<int> st;
//        int i = 0, n = s.size();
//        char op = '+';
//        while (i < n) {
//            if (s[i] == ' ')
//                i++;
//            else if (s[i] >= '0' && s[i] <= '9')
//            {
//                int tmp = 0;
//                while (i < n && s[i] >= '0' && s[i] <= '9')
//                    tmp = tmp * 10 + (s[i++] - '0');
//                if (op == '+')st.push_back(tmp);
//                else if (op == '-')st.push_back(-tmp);
//                else if (op == '*')st.back() *= tmp;
//                else st.back() /= tmp;
//            }
//            else op = s[i++];
//        }
//        int ret = 0;
//        for (auto x : st) ret += x;
//        return ret;
//    }
//};
//class Solution {
//public:
//    string decodeString(string s) {
//        stack<string> st;
//        st.push("");
//        stack<int> nu;
//        int i = 0, n = s.size();
//        while (i < n) {
//            //提取所有数字
//            if (s[i] >= '0' && s[i] <= '9') {
//                int tmp = 0;
//                while (s[i] >= '0' && s[i] <= '9')
//                    tmp = tmp * 10 + (s[i++] - '0');
//                nu.push(tmp);
//            }
//            else if (s[i] == '[') {
//                i++;
//                string tmp;
//                while (s[i] >= 'a' && s[i] <= 'z') tmp += s[i++];
//                st.push(tmp);
//            }
//            else if (s[i] == ']') {
//                string tmp;
//                tmp = st.top();
//                st.pop();
//                int k = nu.top();
//                nu.pop();
//                while (k--) {
//                    st.top() += tmp;
//                }
//                i++;
//            }
//            else {
//                while (i < n && s[i] >= 'a' && s[i] <= 'z')
//                    st.top() += s[i++];
//            }
//        }
//        return st.top();
//    }
//};
//class Solution {
//public:
//    bool validateStackSequences(vector<int>& pushed, vector<int>& popped) {
//        stack<int> st;
//        int i = 0, n = pushed.size();
//        for (auto x : pushed)
//        {
//            st.push(x);
//            while (!st.empty() && st.top() == popped[i])
//            {
//                st.pop();
//                i++;
//            }
//        }
//        return st.empty();
//    }
//};
/*
// Definition for a Node.
class Node {
public:
    int val;
    vector<Node*> children;

    Node() {}

    Node(int _val) {
        val = _val;
    }

    Node(int _val, vector<Node*> _children) {
        val = _val;
        children = _children;
    }
};
*/

//class Solution {
//public:
//    vector<vector<int>> levelOrder(Node* root) {
//        if (root == nullptr) return {};
//        vector<vector<int>>ret;
//        queue <Node*> q;
//        q.push(root);
//        while (q.size())
//        {
//            int sz = q.size();
//            //统计本层的节点个数
//            vector<int> tmp;
//            for (int i = 0; i < sz; i++)
//            {
//                Node* t = q.front();
//                q.pop();
//                tmp.push_back(t->val);
//                for (auto child : t->children)
//                {
//                    if (child != nullptr)
//                        q.push(child);
//                }
//            }
//            ret.push_back(tmp);
//        }
//        return ret;
//    }
//};
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left),
 * right(right) {}
 * };
 */
//class Solution {
//public:
//    vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
//        if (!root)
//            return {};
//        vector<vector<int>> ret;
//        queue<TreeNode*> q;
//        q.push(root);
//        int flag = 1; // false 代表为奇层
//        while (!q.empty()) {
//            int sz = q.size(); // 统计每层几个点数
//            vector<int> tmp;   // 记录当前层的节点个数
//            for (int i = 0; i < sz; i++) {
//                TreeNode* tr = q.front();
//                q.pop();
//                tmp.push_back(tr->val);
//                if (tr->left)
//                    q.push(tr->left);
//                if (tr->right)
//                    q.push(tr->right);
//            }
//            if (flag % 2 == 0)
//                reverse(tmp.begin(), tmp.end());
//            ret.push_back(tmp);
//            flag++;
//        }
//        return ret;
//    }
//};
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left),
 * right(right) {}
 * };
 */
//class Solution {
//public:
//    int widthOfBinaryTree(TreeNode* root) {
//        vector<pair<TreeNode*, unsigned int>> q;
//        q.push_back({ root, 1 });
//        unsigned int ret = 0;
//        while (q.size()) {
//            auto& [x1, y1] = q[0];
//            auto& [x2, y2] = q.back();
//            ret = max(ret, y2 - y1 + 1);
//            vector<pair<TreeNode*, unsigned int>> tmp;
//            for (auto& [x, y] : q) {
//                if (x->left)
//                    tmp.push_back({ x->left, 2 * y });
//                if (x->right)
//                    tmp.push_back({ x->right, 2 * y + 1 });
//            }
//            q = tmp;
//        }
//        return ret;
//    }
//};
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
//class Solution {
//public:
//    vector<int> largestValues(TreeNode* root) {
//        if (!root) return {};
//        vector<int>ret;
//        queue<TreeNode*>q;
//        q.push(root);
//        while (q.size())
//        {
//            int sz = q.size();
//            int tmp = INT_MIN;
//            for (int i = 0; i < sz; i++)
//            {
//                TreeNode* t = q.front();
//                q.pop();
//                tmp = max(tmp, t->val);
//                if (t->left) q.push(t->left);
//                if (t->right)q.push(t->right);
//            }
//            ret.push_back(tmp);
//        }
//        return ret;
//    }
//};
//class Solution {
//public:
//    int lastStoneWeight(vector<int>& stones) {
//        priority_queue<int> pq;
//        for (auto s : stones)
//        {
//            pq.push(s);
//        }
//        while (pq.size() > 1)
//        {
//            int t = pq.top();
//            pq.pop();
//            int x = pq.top();
//            pq.pop();
//            if (t > x)
//            {
//                pq.push(t - x);
//            }
//        }
//        return pq.empty() ? 0 : pq.top();
//    }
//};
//class KthLargest {
//public:
//    priority_queue<int, vector<int>, greater<int>> heap;
//    int _k;
//    KthLargest(int k, vector<int>& nums) {
//        _k = k;
//        for (auto x : nums)
//        {
//            heap.push(x);
//            if (heap.size() > _k) heap.pop();
//        }
//    }
//
//    int add(int val) {
//        heap.push(val);
//        if (heap.size() > _k)
//            heap.pop();
//        return heap.top();
//    }
//};

/**
 * Your KthLargest object will be instantiated and called as such:
 * KthLargest* obj = new KthLargest(k, nums);
 * int param_1 = obj->add(val);
 */
//class Solution {
//    typedef pair<string, int> PSI;
//    struct cmp {
//        bool operator()(const PSI& a, const PSI& b) {
//            // 字典序相同,创建大根堆
//            if (a.second == b.second)
//                return a.first < b.first;
//            // 频次大的，创建小根堆
//            return a.second > b.second;
//        }
//    };
//
//public:
//    vector<string> topKFrequent(vector<string>& words, int k) {
//        unordered_map<string, int> hash;
//        for (auto& s : words)
//            hash[s]++;
//        priority_queue<PSI, vector<PSI>, cmp> heap;
//        for (auto& psi : hash) {
//            heap.push(psi);
//            if (heap.size() > k)
//                heap.pop();
//        }
//        vector<string> ret;
//        while (!heap.empty()) {
//            ret.push_back(heap.top().first);
//            heap.pop();
//        }
//        reverse(ret.begin(), ret.end());
//        return ret;
//    }
//};
//class MedianFinder {
//public:
//    priority_queue<int> left;                             // 创建大根堆
//    priority_queue<int, vector<int>, greater<int>> right; // 创建小根堆
//    MedianFinder() {}
//
//    void addNum(int num) {
//        if (left.size() == right.size()) {
//            if (left.empty() || num <= left.top()) {
//                left.push(num);
//            }
//            else {
//                right.push(num);
//                left.push(right.top());
//                right.pop();
//            }
//        }
//        else {
//            if (num <= left.top()) {
//                left.push(num);
//                right.push(left.top());
//                left.pop();
//            }
//            else {
//                right.push(num);
//            }
//        }
//    }
//
//    double findMedian() {
//        if (left.size() == right.size())
//        {
//            return (left.top() + right.top()) / 2.0;
//        }
//        return left.top();
//    }
//};

/**
 * Your MedianFinder object will be instantiated and called as such:
 * MedianFinder* obj = new MedianFinder();
 * obj->addNum(num);
 * double param_2 = obj->findMedian();
 */
//class Solution {
//    typedef pair<int, int> PII;
//    int dx[4] = { 0, 0, -1, 1 };
//    int dy[4] = { 1, -1, 0, 0 };
//
//public:
//    vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int color) {
//        if (image[sr][sc] == color)
//            return image;
//        int prev = image[sr][sc];
//        queue<PII> q;
//        q.push({ sr, sc });
//        int m = image.size(), n = image[0].size();
//        while (q.size()) {
//            auto [a, b] = q.front();
//            q.pop();
//            image[a][b] = color;
//            for (int i = 0; i < 4; i++) {
//                int x = a + dx[i], y = b + dy[i];
//                if (x >= 0 && x < m && y >= 0 && y < n && image[x][y] == prev) {
//                    q.push({ x, y });
//                }
//            }
//        }
//        return image;
//    }
//};
//class Solution {
//    int dx[4] = { 0, 0, -1, 1 };
//    int dy[4] = { 1, -1, 0, 0 };
//    bool vis[301][301];
//    int r, c;
//
//public:
//    int numIslands(vector<vector<char>>& grid) {
//        int ret = 0;
//        r = grid.size(), c = grid[0].size();
//        for (int i = 0; i < r; i++) {
//            for (int j = 0; j < c; j++) {
//                if (grid[i][j] == '1' && !vis[i][j]) {
//                    ret++;
//                    bfs(grid, i, j);
//                }
//            }
//        }
//        return ret;
//    }
//    void bfs(vector<vector<char>>& grid, int i, int j) {
//        queue<pair<int, int>> q;
//        q.push({ i, j });
//        vis[i][j] = true;
//        while (q.size()) {
//            auto [a, b] = q.front();
//            q.pop();
//            for (int k = 0; k < 4; k++) {
//                int x = a + dx[k];
//                int y = b + dy[k];
//                if (x >= 0 && x < r && y >= 0 && y < c && grid[x][y] == '1' &&
//                    !vis[x][y]) {
//                    q.push({ x, y });
//                    vis[x][y] = true;
//                }
//            }
//        }
//    }
//};
//class Solution {
//    int dx[4] = { 0,0,-1,1 };
//    int dy[4] = { 1,-1,0,0 };
//    int r, c, x;
//public:
//    int maxAreaOfIsland(vector<vector<int>>& grid) {
//        r = grid.size(), c = grid[0].size();
//        int max_area = 0;
//        for (int i = 0; i < r; i++)
//        {
//            for (int j = 0; j < c; j++)
//            {
//                if (grid[i][j] == 1)
//                {
//
//                    int area = bfs(grid, i, j);
//                    max_area = max(max_area, area);
//                }
//            }
//        }
//        return max_area;
//    }
//    int bfs(vector<vector<int>>& grid, int i, int j)
//    {
//        int mi = 0;
//        queue<pair<int, int>>q;
//        q.push({ i,j });
//        grid[i][j] = 0;
//        int area = 1;
//        while (q.size())
//        {
//            auto [a, b] = q.front();
//            q.pop();
//            for (int l = 0; l < 4; l++)
//            {
//                int x = a + dx[l];
//                int y = b + dy[l];
//                if (x >= 0 && x < r && y >= 0 && y < c && grid[x][y] == 1)
//                {
//                    q.push({ x,y });
//                    area++;
//                    grid[x][y] = 0;
//                }
//            }
//        }
//        return area;
//    }
//};
//class Solution {
//    int dx[4] = { 0, 0, -1, 1 };
//    int dy[4] = { 1, -1, 0, 0 };
//    int m, n;
//
//public:
//    void solve(vector<vector<char>>& board) {
//        m = board.size(), n = board[0].size();
//        // 将第一行和最后一行的'O'变为'.'
//        for (int i = 0; i < n; i++) {
//            if (board[0][i] == 'O')
//                bfs(board, 0, i);
//            if (board[m - 1][i] == 'O')
//                bfs(board, m - 1, i);
//        }
//        // 将第一列和最后一列的'O'变为'.'
//        for (int j = 0; j < m; j++) {
//            if (board[j][0] == 'O')
//                bfs(board, j, 0);
//            if (board[j][n - 1] == 'O')
//                bfs(board, j, n - 1);
//        }
//        for (int i = 0; i < m; i++) {
//            for (int j = 0; j < n; j++) {
//                if (board[i][j] == 'O')
//                    board[i][j] = 'X';
//                else if (board[i][j] == '.')
//                    board[i][j] = 'O';
//            }
//        }
//    }
//    void bfs(vector<vector<char>>& board, int i, int j) {
//        queue<pair<int, int>> q;
//        q.push({ i, j });
//        board[i][j] = '.';
//        while (q.size()) {
//            auto [a, b] = q.front();
//            q.pop();
//            for (int i = 0; i < 4; i++) {
//                int x = a + dx[i], y = b + dy[i];
//                if (x >= 0 && x < m && y >= 0 && y < n && board[x][y] == 'O') {
//                    q.push({ x, y });
//                    board[x][y] = '.';
//                }
//            }
//        }
//    }
//};

//class Solution {
//    int dx[4] = { 0,0,-1,1 };
//    int dy[4] = { 1,-1,0,0 };
//public:
//    int nearestExit(vector<vector<char>>& maze, vector<int>& entrance) {
//        int m = maze.size(), n = maze[0].size();
//        bool vis[m][n];
//        memset(vis, 0, sizeof vis);
//        queue<pair<int, int>>q;
//        q.push({ entrance[0],entrance[1] });
//        vis[entrance[0]][entrance[1]] = true;
//        int step = 0;
//        while (q.size())
//        {
//            step++;
//            int sz = q.size();
//            for (int i = 0; i < sz; i++)
//            {
//                auto [a, b] = q.front();
//                q.pop();
//                for (int j = 0; j < 4; j++)
//                {
//                    int x = a + dx[j];
//                    int y = b + dy[j];
//                    if (x >= 0 && x < m && y >= 0 && y < n && maze[x][y] == '.' && !vis[x][y])
//                    {
//                        if (x == 0 || x == m - 1 || y == 0 || y == n - 1) return step;
//                        q.push({ x,y });
//                        vis[x][y] = true;
//                    }
//                }
//            }
//        }
//        return -1;
//    }
//};
//
//class Solution {
//public:
//    int minMutation(string startGene, string endGene, vector<string>& bank) {
//        unordered_set<string> vis; // 用来标记搜索过的状态
//        unordered_set<string> hash(bank.begin(), bank.end());
//        string change = "ACGT";
//        if (startGene == endGene)
//            return 0;
//        if (!hash.count(endGene))
//            return -1;
//
//        queue<string> q;
//        q.push(startGene);
//        vis.insert(startGene);
//        int ret = 0;
//
//        while (q.size()) {
//            ret++;
//            int sz = q.size();
//            while (sz--) {
//                string t = q.front();
//                q.pop();
//                for (int i = 0; i < 8; i++) {
//                    string tmp = t;
//                    for (int j = 0; j < 4; j++) {
//                        tmp[i] = change[j];
//                        if (hash.count(tmp) && !vis.count(tmp)) {
//                            if (tmp == endGene)
//                                return ret;
//                            q.push(tmp);
//                            vis.insert(tmp);
//                        }
//                    }
//                }
//            }
//        }
//        return -1;
//    }
//};
//

//class Solution {
//public:
//    int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
//        unordered_set<string> vis;
//        unordered_set<string> hash(wordList.begin(), wordList.end());
//        if (!hash.count(endWord))
//            return 0;
//        queue<string> q;
//        q.push(beginWord);
//        vis.insert(beginWord);
//        int ret = 1;
//        while (q.size())
//        {
//            ret++;
//            int sz = q.size();
//            while (sz--)
//            {
//                string t = q.front();
//                q.pop();
//                for (int i = 0; i < t.size(); i++)
//                {
//                    string tmp = t;
//                    for (char ch = 'a'; ch <= 'z'; ch++)
//                    {
//                        tmp[i] = ch;
//                        if (!vis.count(tmp) && hash.count(tmp))
//                        {
//                            if (tmp == endWord) return ret;
//                            q.push(tmp);
//                            vis.insert(tmp);
//                        }
//
//                    }
//                }
//            }
//        }
//        return 0;
//    }
//};
//class Solution {
//    int m, n;
//
//public:
//    int cutOffTree(vector<vector<int>>& forest) {
//        m = forest.size(), n = forest[0].size();
//        vector<pair<int, int>> trees;
//        for (int i = 0; i < m; i++) {
//            for (int j = 0; j < n; j++) {
//                if (forest[i][j] > 1)
//                    trees.push_back({ i, j });
//            }
//        }
//        sort(trees.begin(), trees.end(),
//            [&](const pair<int, int>& p1, const pair<int, int>& p2) {
//                return forest[p1.first][p1.second] <
//                    forest[p2.first][p2.second];
//            });
//        // 按照顺序砍树
//        int bx = 0, by = 0;
//        int ret = 0;
//        for (auto& [a, b] : trees) {
//            int step = bfs(forest, bx, by, a, b);
//            if (step == -1)
//                return -1;
//            ret += step;
//            bx = a, by = b;
//        }
//        return ret;
//    }
//    bool vis[51][51];
//    int dx[4] = { 0, 0, -1, 1 };
//    int dy[4] = { 1, -1, 0, 0 };
//    int bfs(vector<vector<int>>& forest, int bx, int by, int ex, int ey) {
//        if (bx == ex && by == ey)
//            return 0;
//        queue<pair<int, int>> q;
//        memset(vis, 0, sizeof vis); // 清空之前的数据
//        q.push({ bx, by });
//        vis[bx][by] = true;
//        int step = 0;
//        while (q.size()) {
//            step++;
//            int sz = q.size();
//            while (sz--) {
//                auto [a, b] = q.front();
//                q.pop();
//                for (int i = 0; i < 4; i++) {
//                    int x = dx[i] + a;
//                    int y = dy[i] + b;
//                    if (x >= 0 && x < m && y >= 0 && y < n && forest[x][y] &&
//                        !vis[x][y]) {
//                        if (x == ex && y == ey)
//                            return step;
//                        q.push({ x, y });
//                        vis[x][y] = true;
//                    }
//                }
//            }
//        }
//        return -1;
//    }
//};
//class Solution {
//    int dx[4] = { 0, 0, -1, 1 };
//    int dy[4] = { 1, -1, 0, 0 };
//
//public:
//    vector<vector<int>> updateMatrix(vector<vector<int>>& mat) {
//        int m = mat.size(), n = mat[0].size();
//        vector<vector<int>> dist(m, vector(n, -1));
//        queue<pair<int, int>> q;
//        for (int i = 0; i < m; i++) {
//            for (int j = 0; j < n; j++) {
//                if (mat[i][j] == 0) {
//                    q.push({ i, j });
//                    dist[i][j] = 0;
//                }
//            }
//        }
//        while (q.size()) {
//            auto [a, b] = q.front();
//            q.pop();
//            for (int i = 0; i < 4; i++) {
//                int x = dx[i] + a, y = dy[i] + b;
//                // dist=-1表示没有搜索过
//                if (x >= 0 && x < m && y >= 0 && y < n && dist[x][y] == -1) {
//                    dist[x][y] = dist[a][b] + 1;
//                    q.push({ x, y });
//                }
//            }
//        }
//        return dist;
//    }
//};
//class Solution {
//    int dx[4] = { 0,0,-1,1 };
//    int dy[4] = { 1,-1,0,0 };
//public:
//    int numEnclaves(vector<vector<int>>& grid) {
//        int m = grid.size(), n = grid[0].size();
//        vector<vector<bool>>vis(m, vector<bool>(n));
//        queue<pair<int, int>>q;
//        for (int i = 0; i < m; i++)
//            for (int j = 0; j < n; j++)
//                if (i == 0 || i == m - 1 || j == 0 || j == n - 1)
//                {
//                    if (grid[i][j] == 1)
//                    {
//                        q.push({ i,j });
//                        vis[i][j] = true;
//                    }
//                }
//        while (q.size())
//        {
//            auto [a, b] = q.front();
//            q.pop();
//            for (int i = 0; i < 4; i++)
//            {
//                int x = dx[i] + a;
//                int y = dy[i] + b;
//                if (x >= 0 && x < m && y >= 0 && y < n && grid[x][y] == 1 && !vis[x][y])
//                {
//                    vis[x][y] = true;
//                    q.push({ x,y });
//                }
//            }
//        }
//        int ret = 0;
//        for (int i = 0; i < m; i++)
//        {
//            for (int j = 0; j < n; j++)
//            {
//                if (grid[i][j] == 1 && !vis[i][j])
//                    ret++;
//            }
//        }
//        return ret;
//    }
////};class Solution {
//int dx[4] = { 0,0,-1,1 };
//int dy[4] = { 1,-1,0,0 };
//public:
//    vector<vector<int>> highestPeak(vector<vector<int>>& isWater) {
//        int m = isWater.size(), n = isWater[0].size();
//        vector<vector<int>>vis(m, vector<int>(n, -1));
//        queue<pair<int, int>>q;
//        for (int i = 0; i < m; i++)
//        {
//            for (int j = 0; j < n; j++)
//            {
//                if (isWater[i][j] == 1)
//                {
//                    q.push({ i,j });
//                    vis[i][j] = 0;
//                }
//            }
//        }
//        while (q.size())
//        {
//            auto [a, b] = q.front();
//            q.pop();
//            for (int i = 0; i < 4; i++)
//            {
//                int x = dx[i] + a, y = dy[i] + b;
//                if (x >= 0 && x < m && y >= 0 && y < n && isWater[x][y] == 0 && vis[x][y] == -1)
//                {
//                    vis[x][y] = vis[a][b] + 1;
//                    q.push({ x,y });
//                }
//            }
//        }
//        return vis;
//    }
//};
//class Solution {
//    int dx[4] = { 0,0,-1,1 };
//    int dy[4] = { 1,-1,0,0 };
//public:
//    int maxDistance(vector<vector<int>>& grid) {
//        int m = grid.size(), n = grid[0].size();
//        vector<vector<int>>dist(m, vector<int>(n, -1));
//        queue<pair<int, int>>q;
//        for (int i = 0; i < m; i++)
//            for (int j = 0; j < n; j++)
//                if (grid[i][j] == 1)
//                {
//                    q.push({ i,j });
//                    dist[i][j] = 0;
//                }
//        int ret = -1;
//        while (q.size())
//        {
//            auto [a, b] = q.front();
//            q.pop();
//            for (int i = 0; i < 4; i++)
//            {
//                int x = dx[i] + a;
//                int y = dy[i] + b;
//                if (x >= 0 && x < m && y >= 0 && y < n && dist[x][y] == -1)
//                {
//                    dist[x][y] = dist[a][b] + 1;
//                    q.push({ x,y });
//                    ret = max(ret, dist[x][y]);
//                }
//            }
//        }
//        return ret;
//    }
//};
//class Solution {
//public:
//    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
//        unordered_map<int, vector<int>>edges;
//        vector<int>in(numCourses);
//        for (auto& e : prerequisites)
//        {
//            int a = e[0], b = e[1];
//            edges[b].push_back(a);
//            in[a]++;
//        }
//        queue<int>q;
//        for (int i = 0; i < numCourses; i++)
//        {
//            if (in[i] == 0)
//                q.push(i);
//        }
//        while (q.size())
//        {
//            int t = q.front();
//            q.pop();
//            for (int a : edges[t])
//            {
//                in[a]--;
//                if (in[a] == 0) q.push(a);
//            }
//        }
//        for (int i = 0; i < numCourses; i++)
//            if (in[i]) return false;
//        return true;
//    }
//};

// class Solution {
// public:
//     vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {
//         vector<vector<int>>edges(numCourses);
//         vector<int>in(numCourses);
//         for(auto & e:prerequisites)
//         {
//             int a = e[0],b = e[1];
//             edges[b].push_back(a);
//             in[a]++;
//         }
//         queue<int>q;
//         vector<int>ret;
//         for(int i = 0;i<numCourses;i++)
//         {
//             if(in[i]==0)
//                 q.push(i);
//         }
//         while(q.size())
//         {
//             int t = q.front();
//             ret.push_back(t);
//             q.pop();
//             for(int a : edges[t])
//             {
//                 in[a]--;
//                 if(in[a]==0) q.push(a);
//             }
//         }
//         if(ret.size()==numCourses) 
//             return ret;
//         else return {};
//     }
// };
//class Solution {
    //     unordered_map<char,unordered_set<char>> edges;
    //     unordered_map<char,int>in;//入度
    //     bool cheak;//边界情况
    // public:
    //     string alienOrder(vector<string>& words) {
    //         //1.建图加初始化入度哈希表
    //         for(auto & s:words)
    //         {
    //             for(auto ch:s)
    //             {
    //                 in[ch] = 0;
    //             }
    //         }
    //         int n  = words.size();
    //         for(int i = 0;i<n;i++)
    //         {
    //             for(int j = i + 1;j<n;j++)
    //             {
    //                 add(words[i],words[j]);
    //                 if(cheak) return "";
    //             }
    //         }
    //         //拓扑排序
    //         queue<char>q;
    //         for(auto &[a,b]:in)
    //         {
    //             if(b==0) q.push(a);
    //         }
    //         string ret;
    //         while(q.size())
    //         {
    //             char t = q.front();q.pop();
    //             ret+=t;
    //             for(char ch : edges[t])
    //             {
    //                 if(--in[ch] == 0)
    //                 q.push(ch);
    //             }
    //         }
    //         for(auto & [a,b]:in)
    //         {
    //             if(b!=0) return "";
    //         }
    //         return ret;
    //     }
    //     void add(string& s1,string &s2)
    //     {
    //         int n = min(s1.size(),s2.size());
    //         int i = 0;
    //         for(;i<n;i++)
    //         {
    //             if(s1[i]!=s2[i])
    //             {
    //                 char a = s1[i],b = s2[i];
    //                 if(!edges.count(a) || !edges[a].count(b))
    //                 {
    //                     edges[a].insert(b);
    //                     in[b]++;
    //                 }
    //                 break;
    //             }
    //         }
    //         if(i == s2.size() && s1.size())
    //         {
    //             cheak = true;
    //         }
    //     }
    // };
//class Solution {
//public:
//    void hanota(vector<int>& A, vector<int>& B, vector<int>& C) {
//        int n = A.size();
//        move(A, B, C, n);
//    }
//    void move(vector<int>& A, vector<int>& B, vector<int>& C, int n) {
//        if (n == 1) {
//            C.push_back(A.back());
//            A.pop_back();
//            return;
//        }
//
//        move(A, C, B, n - 1);
//        C.push_back(A.back());
//        A.pop_back();
//        move(B, A, C, n - 1);
//    }
//};
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
//class Solution {
//public:
//    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
//        if (list1 == nullptr) return list2;
//        if (list2 == nullptr) return list1;
//        if (list1->val <= list2->val)
//        {
//            list1->next = mergeTwoLists(list1->next, list2);
//            return list1;
//        }
//        else
//        {
//            list2->next = mergeTwoLists(list1, list2->next);
//            return list2;
//        }
//    }
//};
//class Solution {
//public:
//    ListNode* reverseList(ListNode* head) {
//        if (!head || !head->next)
//            return head;
//        ListNode* newhead = reverseList(head->next);
//        head->next->next = head;
//        head->next = nullptr;
//        return newhead;
//    }
//};
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
//class Solution {
//public:
//    ListNode* swapPairs(ListNode* head) {
//        if (!head || !head->next)
//            return head;
//        ListNode* tmp = swapPairs(head->next->next);
//        ListNode* ret = head->next;
//        head->next->next = head;
//        head->next = tmp;
//        return ret;
//    }
//};
//class Solution {
//public:
//    double myPow(double x, int n) {
//        return n < 0 ? 1 / pow(x, -(long long)n) : pow(x, n);
//    }
//    double pow(double x, long long n)
//    {
//        if (n == 0) return 1;
//        double tmp = pow(x, n / 2);
//        return n % 2 == 0 ? tmp * tmp : tmp * tmp * x;
//    }
//};
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left),
 * right(right) {}
 * };
 */
//class Solution {
//public:
//    bool evaluateTree(TreeNode* root) {
//        if (!root->right)
//            return root->val == 0 ? false : true;
//        bool left = evaluateTree(root->left);
//        bool right = evaluateTree(root->right);
//        return root->val == 2 ? left | right : left & right;
//    }
//};
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
//class Solution {
//public:
//    int sumNumbers(TreeNode* root) {
//        if (!root) return 0;
//        return dfs(root, 0);
//    }
//    int dfs(TreeNode* root, int persum)
//    {
//        if (!root) return 0;
//        persum = persum * 10 + root->val;
//        if (!root->left && !root->right) return persum;
//        return dfs(root->left, persum) + dfs(root->right, persum);
//    }
//};
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
//class Solution {
//public:
//    TreeNode* pruneTree(TreeNode* root) {
//        if (root == nullptr) return nullptr;
//        root->left = pruneTree(root->left);
//        root->right = pruneTree(root->right);
//        if (root->left == nullptr && root->right == nullptr && root->val == 0)
//        {
//            //delete root;
//            root = nullptr;
//        }
//        return root;
//    }
//};
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left),
 * right(right) {}
 * };
 */
//class Solution {
//    long prev = LONG_MIN;
//
//public:
//    bool isValidBST(TreeNode* root) {
//        if (!root)
//            return true;
//        bool left = isValidBST(root->left);
//        bool cur = false;
//        if (root->val > prev)
//            cur = true;
//        prev = root->val;
//        bool right = isValidBST(root->right);
//        return left && cur && right;
//    }
//};
// /**
//  * Definition for a binary tree node.
//  * struct TreeNode {
//  *     int val;
//  *     TreeNode *left;
//  *     TreeNode *right;
//  *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
//  *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
//  *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
//  * };
//  */
// class Solution {
//     int count ,ret;
// public:
//     int kthSmallest(TreeNode* root, int k) {
//         count = k;
//         dfs(root);
//         return ret;
//     }
//     void dfs(TreeNode * root )
//     {
//         if(root == nullptr || count == 0) return;
//         dfs(root->left);
//         count--;
//         if(count == 0) ret = root->val;
//         dfs(root->right); 
//     }
// };
// /**
//  * Definition for a binary tree node.
//  * struct TreeNode {
//  *     int val;
//  *     TreeNode *left;
//  *     TreeNode *right;
//  *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
//  *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
//  *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
//  * };
//  */
// class Solution {
//     vector<string> ret;
// public:
//     vector<string> binaryTreePaths(TreeNode* root) {
//         string path;
//         dfs(root,path);
//         return ret;
//     }
//     void dfs(TreeNode* root,string path)
//     {
//         path+=to_string(root->val);
//         if(root->left == nullptr && root->right == nullptr)
//         {
//             ret.push_back(path); 
//             return;  
//         }
//         path+="->";
//         if(root->left) dfs(root->left,path);
//         if(root->right) dfs(root->right,path);
//     }
// };
//class Solution {
//    vector<vector<int>>ret;
//    vector<int>path;
//    bool check[7];
//public:
//    vector<vector<int>> permute(vector<int>& nums) {
//        dfs(nums);
//        return ret;
//    }
//    void dfs(vector<int>& nums)
//    {
//        if (nums.size() == path.size())
//        {
//            ret.push_back(path);
//            return;
//        }
//        for (int i = 0; i < nums.size(); i++)
//        {
//            if (check[i] == false)
//            {
//                path.push_back(nums[i]);
//                check[i] = true;
//                dfs(nums);
//                //回溯->恢复现场
//                path.pop_back();
//                check[i] = false;
//            }
//        }
//    }
//};
//class Solution {
//    vector<vector<int>> ret;
//    vector<int> path;
//
//public:
//    vector<vector<int>> subsets(vector<int>& nums) {
//        dfs(nums, 0);
//        return ret;
//    }
//    // 解法一
//    void dfs(vector<int>& nums, int n) {
//        if (nums.size() == n) {
//            ret.push_back(path);
//            return;
//        }
//        // 选
//        path.push_back(nums[n]);
//        dfs(nums, n + 1);
//        path.pop_back();
//        // 不选
//        dfs(nums, n + 1);
//    }
//};
//class Solution {
//    vector<vector<int>> ret;
//    vector<int> path;
//
//public:
//    vector<vector<int>> subsets(vector<int>& nums) {
//        dfs(nums, 0);
//        return ret;
//    }
//    // 解法二
//    void dfs(vector<int>& nums, int n) {
//        ret.push_back(path);
//        for (int i = n; i < nums.size(); i++)
//        {
//            path.push_back(nums[i]);
//            dfs(nums, i + 1);
//            path.pop_back();
//        }
//    }
//};
//class Solution {
//    int ret = 0;
//public:
//    int subsetXORSum(vector<int>& nums) {
//        dfs(nums, 0, 0);
//        return ret;
//    }
//    void dfs(vector<int>& nums, int pos, int path)
//    {
//        ret += path;
//        for (int i = pos; i < nums.size(); i++)
//        {
//            dfs(nums, i + 1, path ^ nums[i]);
//        }
//    }
//};
//class Solution {
//    vector<vector<int>> ret;
//    vector<int>path;
//    bool check[9];
//public:
//    vector<vector<int>> permuteUnique(vector<int>& nums) {
//        sort(nums.begin(), nums.end());
//        dfs(nums, 0);
//        return ret;
//    }
//    void dfs(vector<int>& nums, int pos)
//    {
//        if (nums.size() == pos)
//        {
//            ret.push_back(path);
//            return;
//        }
//        for (int i = 0; i < nums.size(); i++)
//        {
//            //剪枝
//            if (check[i] == true || (i != 0 && nums[i] == nums[i - 1] && check[i - 1] == false))
//                continue;
//            path.push_back(nums[i]);
//            check[i] = true;
//            dfs(nums, pos + 1);
//            path.pop_back();
//            check[i] = false;
//        }
//    }
//};
//class Solution {
//    vector<vector<int>> ret;
//    vector<int> path;
//    bool check[9];
//
//public:
//    vector<vector<int>> permuteUnique(vector<int>& nums) {
//        sort(nums.begin(), nums.end());
//        dfs(nums, 0);
//        return ret;
//    }
//    void dfs(vector<int>& nums, int pos) {
//        if (nums.size() == pos) {
//            ret.push_back(path);
//            return;
//        }
//        for (int i = 0; i < nums.size(); i++) {
//            // 剪枝
//            if (check[i] == false &&
//                (i == 0 || nums[i] != nums[i - 1] || check[i - 1] == true)) {
//                path.push_back(nums[i]);
//                check[i] = true;
//                dfs(nums, pos + 1);
//                path.pop_back();
//                check[i] = false;
//            }
//        }
//    }
//};
//class Solution {
//    string str[10] = { " "," ","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz" };
//    vector<string> ret;
//    string path;
//public:
//    vector<string> letterCombinations(string digits) {
//        if (digits.empty()) return{};
//        dfs(digits, 0);
//        return ret;
//    }
//    void dfs(string digits, int pos)
//    {
//        if (pos == digits.size())
//        {
//            ret.push_back(path);
//            return;
//        }
//        int digits_number = digits[pos] - '0';
//        string letter = str[digits_number];
//        for (int i = 0; i < letter.size(); i++)
//        {
//            path.push_back(letter[i]);
//            dfs(digits, pos + 1);
//            path.pop_back();
//        }
//    }
//};
//class Solution {
//    vector<string> ret;
//    string path;
//
//public:
//    vector<string> generateParenthesis(int n) {
//        dfs(0, 0, n);
//        return ret;
//    }
//    void dfs(int left, int right, int n) {
//        if (right == n && left == n) {
//            ret.push_back(path);
//            return;
//        }
//        if (right > left || left > n)
//            return;
//        path.push_back('(');
//        dfs(left + 1, right, n);
//        path.pop_back();
//        path.push_back(')');
//        dfs(left, right + 1, n);
//        path.pop_back();
//    }
//};
//class Solution {
//    vector<vector<int>> ret;
//    vector<int> path;
//    int n, k;
//
//public:
//    vector<vector<int>> combine(int _n, int _k) {
//        n = _n, k = _k;
//        dfs(1);
//        return ret;
//    }
//    void dfs(int start) {
//        if (path.size() == k) {
//            ret.push_back(path);
//            return;
//        }
//        for (int i = start; i <= n; i++) {
//            path.push_back(i);
//            dfs(i + 1);
//            path.pop_back();
//        }
//    }
//};
//class Solution {
//    int count = 0;
//
//public:
//    int findTargetSumWays(vector<int>& nums, int target) {
//        dfs(nums, target, 0, 0);
//        return count;
//    }
//    void dfs(vector<int>& nums, int target, int pos, int sum) {
//        if (nums.size() == pos) {
//            if (sum == target) {
//                count++;
//            }
//        }
//        else {
//            dfs(nums, target, pos + 1, sum + nums[pos]);
//            dfs(nums, target, pos + 1, sum - nums[pos]);
//        }
//    }
//};
//class Solution {
//    vector<int>path;
//    vector<vector<int>> ret;
//public:
//    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
//        dfs(candidates, target, 0, 0);
//        return ret;
//    }
//    void dfs(vector<int>& candidates, int target, int pos, int sum)
//    {
//        if (sum == target) {
//            ret.push_back(path);
//            return;
//        }
//        if (sum > target || pos > candidates.size()) return;
//        for (int i = pos; i < candidates.size(); i++)
//        {
//            path.push_back(candidates[i]);
//            dfs(candidates, target, i, sum + candidates[i]);
//            path.pop_back();
//        }
//    }
//};
//class Solution {
//    vector<string> ret;
//    string path;
//
//public:
//    vector<string> letterCasePermutation(string s) {
//        dfs(s, 0);
//        return ret;
//    }
//    void dfs(string& s, int pos) {
//        if (pos == s.size()) {
//            ret.push_back(path);
//            return;
//        }
//        // 不变
//        char ch = s[pos];
//        path.push_back(ch);
//        dfs(s, pos + 1);
//        path.pop_back();
//        // 改变
//        if (isalpha(ch)) {
//            char tmp = change(ch);
//            path.push_back(tmp);
//            dfs(s, pos + 1);
//            path.pop_back();
//        }
//    }
//    char change(char ch) {
//        if (isupper(ch))
//            return tolower(ch);
//        if (islower(ch))
//            return toupper(ch);
//        return ch;
//    }
//};
//class Solution {
//    int ret;
//    bool check[16];
//public:
//    int countArrangement(int n) {
//        dfs(1, n);
//        return ret;
//    }
//    void dfs(int pos, int n)
//    {
//        if (n + 1 == pos)
//        {
//            ret++;
//            return;
//        }
//        for (int i = 1; i <= n; i++)
//        {
//            if (!check[i] && (i % pos == 0 || pos % i == 0))
//            {
//                check[i] = true;
//                dfs(pos + 1, n);
//                check[i] = false;
//            }
//        }
//    }
//};
//class Solution {
//    bool checkcol[10];
//    bool checkdig1[20];
//    bool checkdig2[20];
//    vector<vector<string>> ret;
//    vector<string> path;
//
//public:
//    vector<vector<string>> solveNQueens(int n) {
//        path.resize(n);
//        for (int i = 0; i < n; i++)
//            path[i].append(n, '.');
//        dfs(0, n);
//        return ret;
//    }
//    void dfs(int row, int n) {
//        if (row == n) {
//            ret.push_back(path);
//            return;
//        }
//        for (int col = 0; col < n; col++) {
//            //剪枝
//            if (!checkcol[col] && !checkdig1[row - col + n] &&
//                !checkdig2[row + col]) {
//                path[row][col] = 'Q';
//                checkcol[col] = checkdig1[row - col + n] =
//                    checkdig2[row + col] = true;
//                dfs(row + 1, n);
//                //恢复现场
//                path[row][col] = '.';
//                checkcol[col] = checkdig1[row - col + n] =
//                    checkdig2[row + col] = false;
//            }
//        }
//    }
//};
//class Solution {
//    bool row[9][10];
//    bool col[9][10];
//    bool grid[3][3][10];
//
//public:
//    bool isValidSudoku(vector<vector<char>>& board) {
//        for (int i = 0; i < 9; i++) {
//            for (int j = 0; j < 9; j++) {
//                if (board[i][j] != '.') {
//                    int nums = board[i][j] - '0';
//                    if (row[i][nums] || col[j][nums] ||
//                        grid[i / 3][j / 3][nums]) {
//                        return false;
//                    }
//                    row[i][nums] = col[j][nums] = grid[i / 3][j / 3][nums] =
//                        true;
//                }
//            }
//        }
//        return true;
//    }
//};
//class Solution {
//    bool row[9][10];
//    bool col[9][10];
//    bool grid[3][3][10];
//public:
//    void solveSudoku(vector<vector<char>>& board) {
//        for (int i = 0; i < 9; i++)
//        {
//            for (int j = 0; j < 9; j++)
//            {
//                if (board[i][j] != '.')
//                {
//                    int nums = board[i][j] - '0';
//                    row[i][nums] = col[j][nums] = grid[i / 3][j / 3][nums] = true;
//                }
//            }
//        }
//        dfs(board);
//    }
//    bool dfs(vector<vector<char>>& board)
//    {
//
//        for (int i = 0; i < 9; i++)
//        {
//            for (int j = 0; j < 9; j++)
//            {
//                if (board[i][j] == '.')
//                {
//                    for (int m = 1; m <= 9; m++)
//                    {
//                        if (!row[i][m] && !col[j][m] && !grid[i / 3][j / 3][m])
//                        {
//                            board[i][j] = '0' + m;
//                            row[i][m] = col[j][m] = grid[i / 3][j / 3][m] = true;
//                            if (dfs(board) == true) return true;
//                            //恢复现场
//                            board[i][j] = '.';
//                            row[i][m] = col[j][m] = grid[i / 3][j / 3][m] = false;
//                        }
//                    }
//                    return false;
//                }
//            }
//        }
//        return true;
//    }
//};
//class Solution {
//public:
//    bool exist(vector<vector<char>>& board, string word) {
//        vector<vector<bool>> visit(board.size(), vector<bool>(board[0].size(), false));
//        for (int i = 0; i < board.size(); i++)
//        {
//            for (int j = 0; j < board[0].size(); j++)
//            {
//                if (board[i][j] == word[0])
//                {
//                    if (dfs(board, i, j, visit, word, 0))
//                        return true;
//                }
//            }
//        }
//        return false;
//    }
//    bool dfs(vector<vector<char>>& board, int i, int j, vector<vector<bool>>& visit, string& word, int pos)
//    {
//        if (pos == word.size())
//        {
//            return true;
//        }
//        if (i < 0 || j < 0 || i >= board.size() || j >= board[0].size()) return false;
//        if (visit[i][j] || board[i][j] != word[pos]) return false;
//        visit[i][j] = true;
//        bool ret = dfs(board, i + 1, j, visit, word, pos + 1) ||
//            dfs(board, i - 1, j, visit, word, pos + 1) ||
//            dfs(board, i, j + 1, visit, word, pos + 1) ||
//            dfs(board, i, j - 1, visit, word, pos + 1);
//        visit[i][j] = false;
//        return ret;
//    }
//};
//class Solution {
//    bool visit[7][7];
//    int m, n;
//public:
//    bool exist(vector<vector<char>>& board, string word) {
//        m = board.size(), n = board[0].size();
//        for (int i = 0; i < m; i++)
//        {
//            for (int j = 0; j < n; j++)
//            {
//                if (board[i][j] == word[0])
//                {
//                    visit[i][j] = true;
//                    if (dfs(board, i, j, word, 1))
//                    {
//                        return true;
//                    }
//                    visit[i][j] = false;
//                }
//            }
//        }
//        return false;
//    }
//    int dx[4] = { 0,0,-1,1 };
//    int dy[4] = { 1,-1,0,0 };
//    bool dfs(vector<vector<char>>& board, int i, int j, string word, int pos)
//    {
//        if (pos == word.size())
//            return true;
//        for (int k = 0; k < 4; k++)
//        {
//            int x = dx[k] + i, y = dy[k] + j;
//            if (x >= 0 && x < m && y >= 0 && y < n && !visit[x][y] && board[x][y] == word[pos])
//            {
//                visit[x][y] = true;
//                if (dfs(board, x, y, word, pos + 1)) return true;
//                visit[x][y] = false;
//            }
//        }
//        return false;
//    }
//};
//class Solution {
//    int dx[4] = { 0, 0, -1, 1 };
//    int dy[4] = { 1, -1, 0, 0 };
//    int gold;
//    int m, n;
//
//public:
//    int getMaximumGold(vector<vector<int>>& grid) {
//        m = grid.size(), n = grid[0].size();
//        for (int i = 0; i < m; i++) {
//            for (int j = 0; j < n; j++) {
//                if (grid[i][j] != 0)
//                    dfs(grid, i, j, 0);
//            }
//        }
//        return gold;
//    }
//    void dfs(vector<vector<int>>& grid, int i, int j, int cur) {
//        cur += grid[i][j];
//        gold = max(gold, cur);
//        int tmp = grid[i][j];
//        grid[i][j] = 0;
//        for (int k = 0; k < 4; k++) {
//            int x = dx[k] + i;
//            int y = dy[k] + j;
//            if (x >= 0 && x < m && y >= 0 && y < n && grid[x][y] != 0)
//                dfs(grid, x, y, cur);
//        }
//        grid[i][j] = tmp;
//    }
//};
//class Solution {
//    int dx[4] = { 0,0,1,-1 };
//    int dy[4] = { 1,-1,0,0 };
//    int ret;
//    int m, n;
//    bool check[20][20];
//    int TotalEmpty;
//public:
//    int uniquePathsIII(vector<vector<int>>& grid) {
//        m = grid.size(), n = grid[0].size();
//        int sx, sy;
//        for (int i = 0; i < m; i++)
//        {
//            for (int j = 0; j < n; j++)
//            {
//                if (grid[i][j] != -1) TotalEmpty++;
//                if (grid[i][j] == 1) sx = i, sy = j;
//            }
//        }
//        check[sx][sy] = true;
//        dfs(grid, sx, sy, 1);
//        return ret;
//    }
//    void dfs(vector<vector<int>>& grid, int i, int j, int count)
//    {
//        if (grid[i][j] == 2)
//        {
//            if (count == TotalEmpty) ret++;
//            return;
//        }
//        for (int k = 0; k < 4; k++)
//        {
//            int x = dx[k] + i, y = dy[k] + j;
//            if (x >= 0 && x < m && y >= 0 && y < n && !check[x][y] && grid[x][y] != -1)
//            {
//                check[x][y] = true;
//                dfs(grid, x, y, count + 1);
//                check[x][y] = false;
//            }
//        }
//    }
//};
//class Solution {
//    int dx[4] = { 0,0,1,-1 };
//    int dy[4] = { 1,-1,0,0 };
//    int prev;
//    int m, n;
//public:
//    vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int color) {
//        if (image[sr][sc] == color)
//            return image;
//        m = image.size(), n = image[0].size();
//        prev = image[sr][sc];
//        dfs(image, sr, sc, color);
//        return image;
//    }
//    void dfs(vector<vector<int>>& image, int sr, int sc, int color)
//    {
//
//        image[sr][sc] = color;
//        for (int k = 0; k < 4; k++)
//        {
//            int x = dx[k] + sr;
//            int y = dy[k] + sc;
//            if (x >= 0 && x < m && y >= 0 && y < n && image[x][y] == prev)
//            {
//                dfs(image, x, y, color);
//            }
//        }
//
//    }
//};
//class Solution {
//    int dx[4] = { 0,0,-1,1 };
//    int dy[4] = { -1,1,0,0 };
//    int m, n;
//    bool vis[301][301];
//public:
//    int numIslands(vector<vector<char>>& grid) {
//        m = grid.size(), n = grid[0].size();
//        int ret = 0;
//        for (int i = 0; i < m; i++)
//        {
//            for (int j = 0; j < n; j++)
//            {
//                if (!vis[i][j] && grid[i][j] == '1')
//                {
//                    ret++;
//                    dfs(grid, i, j);
//                }
//            }
//        }
//        return ret;
//    }
//    void dfs(vector<vector<char>>& grid, int i, int j)
//    {
//        vis[i][j] = true;
//        for (int k = 0; k < 4; k++)
//        {
//            int x = dx[k] + i, y = dy[k] + j;
//            if (x >= 0 && x < m && y >= 0 && y < n && !vis[x][y] && grid[x][y] == '1')
//            {
//                dfs(grid, x, y);
//            }
//        }
//    }
//};
//class Solution {
//    int dx[4] = { 0,0,1,-1 };
//    int dy[4] = { 1,-1,0,0 };
//    int m, n;
//    bool vis[51][51];
//    int ans;
//    int count;
//public:
//    int maxAreaOfIsland(vector<vector<int>>& grid) {
//        m = grid.size(), n = grid[0].size();
//        for (int i = 0; i < m; i++)
//        {
//            for (int j = 0; j < n; j++)
//            {
//                if (!vis[i][j] && grid[i][j] == 1)
//                {
//                    count = 0;
//                    dfs(grid, i, j);
//                    ans = max(ans, count);
//                }
//            }
//        }
//        return ans;
//    }
//    void dfs(vector<vector<int>>& grid, int i, int j)
//    {
//        vis[i][j] = true;
//        count++;
//        for (int k = 0; k < 4; k++)
//        {
//            int x = dx[k] + i, y = dy[k] + j;
//            if (x >= 0 && x < m && y >= 0 && y < n && !vis[x][y] && grid[x][y] == 1)
//            {
//                dfs(grid, x, y);
//            }
//        }
//    }
//};
//class Solution {
//    int dx[4] = { 0,0,-1,1 };
//    int dy[4] = { -1,1,0,0 };
//    int m, n;
//    bool vis[201][201];
//public:
//    void solve(vector<vector<char>>& board) {
//        m = board.size(), n = board[0].size();
//        for (int i = 0; i < m; i++)
//        {
//            if (board[i][0] == 'O' && !vis[i][0]) dfs(board, i, 0);
//            if (board[i][n - 1] == 'O' && !vis[i][n - 1]) dfs(board, i, n - 1);
//        };
//        for (int i = 0; i < n; i++)
//        {
//            if (board[0][i] == 'O' && !vis[0][i]) dfs(board, 0, i);
//            if (board[m - 1][i] == 'O' && !vis[m - 1][i]) dfs(board, m - 1, i);
//        }
//        for (int i = 0; i < m; i++)
//        {
//            for (int j = 0; j < n; j++)
//            {
//                if (!vis[i][j] && board[i][j] == 'O') board[i][j] = 'X';
//            }
//        }
//    }
//    void dfs(vector<vector<char>>& board, int i, int j)
//    {
//        vis[i][j] = true;
//        for (int k = 0; k < 4; k++)
//        {
//            int x = dx[k] + i;
//            int y = dy[k] + j;
//            if (x >= 0 && x < m && y >= 0 && y < n && !vis[x][y] && board[x][y] == 'O')
//                dfs(board, x, y);
//        }
//    }
//};
//class Solution {
//    int m, n;
//    int dx[4] = { 0,0,-1,1 };
//    int dy[4] = { -1,1,0,0 };
//public:
//    vector<vector<int>> pacificAtlantic(vector<vector<int>>& heights) {
//        m = heights.size(), n = heights[0].size();
//        vector<vector<bool>> Pacific(m, vector<bool>(n, false));
//        vector<vector<bool>> Altantic(m, vector<bool>(n, false));
//        vector<vector<int>>ret;
//        for (int i = 0; i < m; i++) dfs(i, 0, Pacific, heights);
//        for (int i = 0; i < n; i++) dfs(0, i, Pacific, heights);
//        for (int i = 0; i < n; i++) dfs(m - 1, i, Altantic, heights);
//        for (int i = 0; i < m; i++) dfs(i, n - 1, Altantic, heights);
//        for (int i = 0; i < m; i++)
//        {
//            for (int j = 0; j < n; j++)
//            {
//                if (Pacific[i][j] && Altantic[i][j])
//                {
//                    ret.push_back({ i,j });
//                }
//            }
//        }
//        return ret;
//    }
//    void dfs(int i, int j, vector<vector<bool>>& Ocean, vector<vector<int>>& heights)
//    {
//        if (Ocean[i][j]) return;
//        Ocean[i][j] = true;
//        for (int k = 0; k < 4; k++)
//        {
//            int x = dx[k] + i;
//            int y = dy[k] + j;
//            if (x >= 0 && x < m && y >= 0 && y < n && !Ocean[x][y] && heights[x][y] >= heights[i][j])
//                dfs(x, y, Ocean, heights);
//        }
//    }
//};
//class Solution {
//    int dx[8] = { 0, 0, -1, 1, 1, -1, -1, 1 };
//    int dy[8] = { -1, 1, 0, 0, 1, -1, 1, -1 };
//    int m, n;
//
//public:
//    vector<vector<char>> updateBoard(vector<vector<char>>& board,
//        vector<int>& click) {
//        if (board[click[0]][click[1]] == 'M') {
//            board[click[0]][click[1]] = 'X';
//            return board;
//        }
//        m = board.size(), n = board[0].size();
//        dfs(board, click[0], click[1]);
//        return board;
//    }
//    void dfs(vector<vector<char>>& board, int i, int j) {
//        if (board[i][j] != 'E')
//            return;
//        int ans = 0;
//        // 先统计炸弹的数量
//        for (int k = 0; k < 8; k++) {
//            int x = dx[k] + i;
//            int y = dy[k] + j;
//            if (x >= 0 && x < m && y >= 0 && y < n && board[x][y] == 'M') {
//                ans++;
//            }
//        }
//        if (ans > 0) {
//            board[i][j] = '0' + ans;
//        }
//        else {
//            board[i][j] = 'B';
//            for (int k = 0; k < 8; k++) {
//                int x = dx[k] + i;
//                int y = dy[k] + j;
//                if (x >= 0 && x < m && y >= 0 && y < n) {
//                    dfs(board, x, y);
//                }
//            }
//        }
//    }
//};
//class Solution {
//    int dx[2] = { 0,1 };
//    int dy[2] = { 1,0 };
//    int ret;
//public:
//    int wardrobeFinishing(int m, int n, int cnt) {
//        vector<vector<int>>grid(m, vector<int>(n));
//        vector<vector<bool>>vis(m, vector<bool>(n, false));
//        dfs(0, 0, vis, m, n, cnt);
//        return ret;
//    }
//    void dfs(int i, int j, vector<vector<bool>>& vis, int m, int n, int cnt)
//    {
//        if (i >= m || i < 0 || j >= n || j < 0 || vis[i][j] || digit(i) + digit(j) > cnt) return;
//        vis[i][j] = true;
//        ret++;
//        for (int k = 0; k < 2; k++)
//        {
//            int x = dx[k] + i, y = dy[k] + j;
//            if (x >= 0 && x < m && y >= 0 && y < n)
//            {
//
//                dfs(x, y, vis, m, n, cnt);
//            }
//        }
//    }
//    int digit(int x)
//    {
//        int tmp = 0;
//        while (x > 0)
//        {
//            tmp += x % 10;
//            x /= 10;
//        }
//        return tmp;
//    }
//};
//class Solution {
//    int m, n, cnt;
//    int dx[2] = { 0,1 };
//    int dy[2] = { 1,0 };
//    bool vis[101][101];
//    int ret;
//public:
//    int wardrobeFinishing(int _m, int _n, int _cnt) {
//        m = _m, n = _n, cnt = _cnt;
//        vector<vector<int>>grid(m, vector<int>(n));
//        dfs(0, 0);
//        return ret;
//    }
//    void dfs(int i, int j)
//    {
//        ret++;
//        vis[i][j] = true;
//        for (int k = 0; k < 2; k++)
//        {
//            int x = dx[k] + i;
//            int y = dy[k] + j;
//            if (x >= 0 && x < m && y >= 0 && y < n && !vis[x][y] && check(x, y))
//            {
//                dfs(x, y);
//            }
//        }
//    }
//    bool check(int i, int j)
//    {
//        int tmp = 0;
//        while (i)
//        {
//            tmp += i % 10;
//            i /= 10;
//        }
//        while (j)
//        {
//            tmp += j % 10;
//            j /= 10;
//        }
//        return tmp <= cnt;
//    }
//};
//int main();